Emparejamiento de gráficos cúbicos de 3 conexiones

Question

He estado haciendo algo de teoría de grafos recreativa, y me he encontrado con un problema que no consigo resolver.

El problema: Dejemos que e sea una arista de un gráfico cúbico de 3 conexiones G . Demostrar que existe un emparejamiento perfecto que cubre e.

Ahora bien, sé que cualquier grafo cúbico sin puentes tiene algún emparejamiento perfecto (teorema de Peterson, que se deduce de la fórmula de Tutte-Berge), pero no veo una extensión natural a los grafos cúbicos de 3 conexiones. Mi primera idea es eliminar u & v (si e \= { u , v }), pero entonces sólo tienes un grafo conectado que estás tratando de cubrir con una coincidencia perfecta. Mi otro pensamiento es que usted podría eliminar los otros dos bordes todavía incidente con (WLOG) v ya que un grafo de 3 conexiones es al menos de 3 aristas (en este caso, exactamente de 3 aristas), pero eso no me lleva a ninguna parte. Cualquier pista o paso en la dirección correcta sería útil.

Answer 1

Dejemos que $e=uv$ sea una arista de $G$ . Dejemos que $f$ y $g$ sean las otras dos aristas incidentes con $v$ . Dejemos que $G'=G-f-g$ .

Reclamación 1: $G'-v$ es de 2 conexiones.

$G'-v$ es lo mismo que $G-v$ .

Reclamación 2: $G'$ tiene una correspondencia perfecta.

Puedes demostrarlo mostrando directamente que la condición de Tutte se cumple. Asumo que estás familiarizado con la prueba estándar del teorema de Petersen, por lo que no me extenderé en cada detalle. Tenga en cuenta que $G'$ tiene sólo 2 vértices de grado par.

Dejemos que $S$ sea un subconjunto de vértices de $G$ , $o(G'-S)$ el número de componentes impar de $G'-S$ . Como máximo un componente de impar puede contener $v$ ese componente puede tener tan solo 1 arista para $S$ (ya que $G'$ sigue conectado). Todos los demás componentes de impar contienen un vértice diferente de $v$ Así que porque $G'-v$ es de 2 conexiones todos los demás componentes de impar tienen al menos 2 aristas a $S$ . Como máximo dos componentes Impares pueden contener un vértice de grado par (incluso en $G'$ ). Todos los demás componentes de impar deben tener al menos tres bordes para $S$ (como en la prueba estándar del teorema de Petersen).

Dejemos que $x$ sea el número de aristas entre $S$ y los componentes impar de $G'-S$ . Acabamos de demostrar que $x\geq 3o(G'-S)-4$ .

Por otro lado $S$ puede acomodar como máximo $3|S|$ bordes, por lo que $x\leq3|S|$ .

Esto significa que $o(G'-S)\leq|S|+\frac{4}{3}$ .

Ahora, finalmente, utiliza el hecho de que $G$ es par, por lo que $o(G'-S)$ y $|S|$ tienen la misma paridad. Esto demuestra que $o(G'-S)\leq|S|$ y se cumple la condición de Tutte.

Argumento final: la perfecta coincidencia de $G'$ es una coincidencia perfecta de $G$ y contiene $e$ , ya que el grado de $v$ en $G'$ es 1.