El gráfico de Petersen es de 3 conexiones

Question

Esto es obvio, pero ¿hay una forma sencilla/elegante de demostrar que el grafo de Petersen no tiene cortes de vértices de tamaño 2?

Uno podría simplemente mirar todos los posibles cortes de vértices de tamaño 2 y observar que no desconectan el gráfico, pero técnicamente hay ${10 \choose 2} = 45$ posibilidades. En realidad, la mayoría de estos cortes dan como resultado el mismo gráfico (conectado).

Así que sólo pido una forma clara y sencilla de demostrar que no hay cortes de vértices de tamaño 2.

Answer 1

Piensa en lo que ocurre cuando eliminas los vértices uno a uno.

Reclamación 1 Si eliminamos un vértice del gráfico de Petersen, obtenemos un gráfico hamiltoniano.

Esto se deduce inmediatamente: es irrelevante qué vértice eliminamos, por simetría, y una vez que eliminamos un vértice es fácil encontrar un Ciclo Hamiltoniano.

Reclamación 2 Si eliminamos un vértice de un grafo hamiltoniano, obtenemos un grafo conexo. (En realidad, obtenemos un grafo que tiene un camino hamiltoniano).

Prueba: El ciclo hamiltoniano se convierte en un camino hamiltoniano después de borrar el vértice.

Nota: En la reivindicación 2, no he dicho que el gráfico se convierta en semi-hamiltoniano porque podría seguir siendo hamitoniano (por ejemplo $K_n$ tiene esta propiedad).

Answer 2

Observamos que el gráfico de Petersen está formado por dos circuitos disjuntos de longitud $5$ y una perfecta coincidencia entre estos dos grupos de $5$ vértices. Si eliminamos dos vértices en uno de estos dos circuitos, definitivamente seguirá conectado, ya que seguimos teniendo un circuito de longitud $5$ y aristas coincidentes que conectarán los vértices restantes en otro circuito. Si eliminamos un vértice de cada uno de estos dos circuitos, entonces sigue conectado, ya que se convierten en dos caminos de longitud $4$ y todavía hay algún borde de coincidencia que los conecta.