Si $G$ es biconnected y $\delta(G) \geq 3 \Rightarrow \exists v: G-v$ es también biconnected.
Donde $\delta (G) - $ mínimo grado de todos los vértices, $G-v$ es igual a que si eliminamos este vértice de $G$
Dar alguna pista por favor!
Gracias!
Respuestas
¿Demasiados anuncios?
Desafortunadamente, la mayoría de lo que puedo hacer es proporcionar una referencia para el resultado.
Mucho más instrucción que la que está en cuestión es probado aquí en el papel Críticamente $n$-conectado gráficos por Gary Chartrand, Agnis Kaugars y Don R. Lamer.
Específicamente se define un críticamente $n$-gráfica conectada a una $n$-gráfica conectada para que la eliminación de cualquier vértice reducirá la conectividad $1$. Ellos nos demuestran que ninguna de tales gráficos deben tener un vértice de grado menor que $\frac{3n-1}{2}$ (y que esta obligado no puede ser mejorado).
Ellos hacen referencia a un documento [Un teorema sobre la eliminación de vértices a partir de bloques por A. Kaugars] que demuestre explícitamente el caso de $n=2$ que es lo que nos interesa. Por desgracia, no parece fácil de obtener acceso a dicho papel (a menos que alguien de aquí pasa a asistir a la Kalamazoo College).
lakshmanaraj
Puntos
3145
No es una respuesta completa, pero podría ser útil una dirección (he no he seguido todo el camino a través de).
Considere la posibilidad de un máximo de camino de $x_0 x_1 \ldots x_n$$G$. Porque es la máxima, a todos los vecinos de $x_0, x_n$ mus estar en el camino en sí (véase también http://math.stackexchange.com/a/212052/44541), y debido a la bi-conectividad, es en realidad un ciclo (como $x_0$ $x_n$ debe estar conectado directamente.
Si examinamos todos los otros vértices en la gráfica, todos los vecinos están en la gráfica (o hemos sido capaces de construir un camino más largo debido a la bi-conectividad con el prójimo, no en el ciclo. Esto crea una máxima del ciclo, donde cada vértice es también parte de un acorde borde.
Intuitivamente, esto debe asegurarse de que hay suficientes forma de "bypass" uno de los vértices, como cumplir con la declaración. Pero no he perseguido más todavía.
