2-gráfica conectada problema (West, Introducción a la Teoría de grafos, ex. 4.2.15)

Question

Estoy luchando con este problema durante horas, pero parece ser fácil. Aquí está el problema:

La prueba de que cada vértice $v$ 2-gráfica conectada $G$ ha prójimo $u$ tal que $G - v - u$ está conectado.

Cualquier ayuda es muy apreciada! Creo que puede ser que falte un trivial solución aquí =(

EDITAR: Hasta ahora, he tratado de crear un proceso gradual que dará una adecuada vecino vértice seleccionado $v$. Así, uno puede remover $v$ y cualquier $v$'s prójimo $u$$G$. El gráfico resultante puede ser conectado o no. Si está conectado, entonces hemos encontrado a nuestro prójimo y puede detener el proceso. De lo contrario, el Gráfico de $G$ está empalmado en varios componentes. Es claro que en cada componente debe ser de al menos un vecino de $v$ $G$ 2-conectado. Creo que en este paso que debo elegir uno de estos vecinos y quitar en lugar de la inicial $u$. Pero no puedo encontrar la prueba de que no va a llevar a otra de corte de la gráfica.

Answer 1

Deje $G$ ser nuestras 2-gráfica conectada, $v$ un vértice arbitrario de $G$. Si $G-v$ es todavía 2-conectado, podemos tomar cualquier vecino de $v$.

De lo contrario, el bloque de árbol de $G-v$ tiene una hoja bloque $B$. Deje $w$ el (único) de corte vértice de $G-v$$B$. $v$ debe tener un vecino$u$$B-w$, o de otra manera $G-w$ sería desconectado(!)

Desde $B$ 2, $B-u$ está conectado, por lo $G-v-u$ está conectado.