Demostrar que estos gráficos no son isomorfos

Question

Tengo estos tres gráficos (en la imagen de abajo, perdón por la mala calidad está en microsoft paint)

Necesito ayuda para demostrar que X no es isomorfo a Y y que X no es isomorfo a Z.

Tengo una solución muy poco elegante OMI en la que examino la distancia de cada vértice individual a los otros 11, clasificándolos en base a eso, y mostrando que una clase tiene cuatro vértices que están conectados en una pero que no están conectados en la otra.

Me gustaría ver una solución más elegante en la que el isomorfismo se demuestre mediante un argumento escrito (¡sin matrices de adyacencia, por favor!).

Answer 1

Ninguna de sus tres gráficas es isomorfa.

$X$ no es isomorfo a $Y$ o $Z$ porque $X$ es $2$ -colorables, mientras que $Y$ y $Z$ contienen $5$ -ciclos.

$Y$ no es isomorfo a $X$ o $Z$ porque $Y$ es plana, mientras que $X$ y $Z$ contienen subgrafos isomorfos a subdivisiones de $K_{3,3}.$