Si hay un ciclo que contiene aristas $a, b$ y otra que contiene aristas $b, c$ entonces existe un ciclo que contiene $a, c$

Question

Dado un grafo simple conexo no dirigido $G$ que contiene aristas $a, b, c$ Me gustaría demostrar que si $\exists$ un ciclo $C_1$ que contiene aristas $a$ y $b$ y un ciclo $C_2$ que contiene bordes $b$ y $c$ entonces debe existir un ciclo $C_3$ que contiene aristas $a$ y $c$ .

Sea $a=\{u_a,v_a\}, b=\{u_b,v_b\}, c=\{u_c,v_c\}$ .

He descompuesto los ciclos de la siguiente manera:

$C_1=\{u_a,a,v_a,(\text{Part A}),u_b,b,v_b,(\text{Part B}),u_a\}$

$C_2=\{u_b,b,v_b,(\text{Part C}),u_c,c,v_c,(\text{Part D}),u_b\}$

Si los ciclos no se cruzan, entonces funciona lo siguiente:

$C_3=\{u_a,a,v_a,(\text{Part A}),u_b,b,v_b,(\text{Part C}),u_c,c,v_c,(\text{Part D}),u_b,b,v_b,(\text{Part B}),u_a\}$

Sin embargo, esto no funciona si las piezas $A$ o $B$ compartir vértices con partes $C$ o $D$ .

¿Cómo puedo demostrar que la afirmación inicial es cierta en todos los casos? Gracias.

Answer 1

Usando la notación del OP:

Considerar el ciclo $C_1$ incluidos los bordes $a$ y $b$ . Sin pérdida de generalidad, podemos decir que existe una cadena (grafo lineal, Parte $A$ ) del vértice $v_a$ a $u_b$ y una cadena (grafo lineal, Parte $B$ ) del vértice $u_a$ a $v_b$ . Para simplificar, incluimos los vértices finales, $v_a$ y $u_b$ en Parte $A$ y vértices $u_a$ y $v_b$ en Parte $B$ .

Porque hay un ciclo $C_3$ incluido el borde $c$ y borde $b$ ese ciclo debe pasar por $u_b$ y $v_b$ . Por tanto, el ciclo debe pasar al menos por un vértice de la Parte $A$ y un vértice en Parte $B$ .

Llame a $u_1$ el vértice en $C_3$ en Parte $A$ que esté más cerca de $v_a$ . Un camino desde $u_1$ conduce al borde $c$ sin pasar por $b$ . Llama a esa ruta Parte $C$ . (Sin pérdida de generalidad, podemos suponer que Parte $C$ incluye $u_c$ .)

Llame a $u_2$ el vértice en $C_3$ en Parte $B$ que esté más cerca de $u_a$ . Un camino desde $u_2$ conduce al otro vértice de la arista $c$ (es decir, $v_c$ ). Llamar a la ruta de $u_2$ a $v_c$ Pieza $D$ .

Un ciclo que contiene $a$ y $c$ es así:

• borde $a$
• De $v_a$ a $u_1$ a lo largo de una parte $A$
• De $u_1$ a $u_c$ a lo largo de la parte $C$
• borde $c$
• De $v_c$ a $u_2$ a lo largo de una parte $D$
• De $u_2$ a $u_a$ a lo largo de una parte $B$

Informalmente, estamos encontrando el vértice en $C_3$ en Parte $A$ más cercano a $a$ en "un lado" (es decir, a $v_a$ ) e igualmente el vértice en $C_3$ más cercano a $a$ en el "otro lado" (es decir, a $u_a$ ) y, a continuación, sustituir la ruta de $u_1$ a $u_2$ en $C_3$ con la trayectoria lineal desde $u_1$ a $v_a$ a $a$ a $u_a$ a $u_2$ .