Demostrar que dos grafos son isomorfos

Question

Acabo de encontrar un viejo libro sobre teoría de números y teoría de grafos que utilicé en mi primer curso en la universidad hace muchos años. Mirando en su interior, he encontrado una nota manuscrita señalando un problema que dice:

• Demostrar que todos los $(k-2)$ -subgrafos regulares de $K_k$ son isomorfas a $K_{k-1}$ donde $k$ es un número entero impar.

Estuve pensando en ello, pero lo único que me vino a la mente es la propiedad que dice que la suma de los grados de todos los vértices es igual al doble del número de aristas, pero no sé si esto puede ser útil. Agradecería cualquier pista para demostrarlo.

Answer 1

Toma un $(k-2)$ -subgrafo regular $\Gamma$ tiene como máximo $k$ vértices (de hecho, debe tener o bien $k-1$ o $k$ vértices) por lo que cualquier vértice $x$ tiene como máximo un no vecino (excluyéndose a sí mismo). Supongamos que $\Gamma$ no está completa, por lo que $|V(\Gamma)| = k$ y hay un vértice $x$ con un único no vecino $y$ de hecho, en este caso, cada vértice debe tener un único no-vecino en $\Gamma$ . ¿Esto ayuda (recuerde que $k$ es impar)?