La condición de regular los gráficos

Question

Estoy tratando de hacer esta teoría de grafos ejercicio:

Vamos gráfico de $G$ no contiene triángulo y para cada desconectado los vértices de $G$ existe exactamente dos vértices que son vecinos de ambos. Demuestra que el gráfico es regular.

Puedo imaginar que sólo dos casos de los gráficos de $K_2$$C_4$. Hay otros gráficos? Necesito sugerencia de cómo crearlas.

Answer 1

Una vez que usted sabe que el grafo es regular, se deduce que el gráfico está fuertemente regular con los parámetros de $$ \binom{k}{2}+1,\ k,\ 0,\ 2. $$ Además de los 4-ciclo, hay otros dos ejemplos - El Gewirtz gráfico en 56 de los vértices con $k=10$ y el uno en el otro ejemplo, conocido como el Clebsch gráfico. Creo que los detalles son todos en Biggs del libro "Finito de Grupos de Automorfismos".

Answer 2

Aquí es una prueba de por qué los títulos han de ser iguales. Deje $p$ ser cualquier nodo y $k = \deg(p)$ su grado. Suponga $p$ es adyacente a los nodos de $v_1, v_2, \ldots, v_k$. Queremos mostrar que $\deg(v_i) = k$.

En primer lugar, desde el triángulo condición, ninguna de las $v_i$ son adyacentes. Ya que no son adyacentes podemos, para cualquier par de vértices $v_i, v_j$, encontramos un vértice $w$ que es adyacente a los dos. Tenga en cuenta que esta $w$ es distinta para todos los pares de $v_i, v_j$, de lo contrario $w$ $p$ compartir más de dos vecinos.

Por lo tanto, con todos estos bordes añadidos tenemos que $\deg(v_i) = \deg(p)$ (agregar en uno de los bordes de cada una de las otras $v_j$).

Lo que tenemos que mostrar ahora es que no hay manera de que podamos añadir más bordes cualquier $v_i$. Suponga $q$ es adyacente a $v_i$, y dado que no es adyacente a $p$, a algunos $v_j$. Pero ahora $v_i, v_j$ tiene tres vecinos: $w, p, q$. Contradicción.

editar el siguiente parece ser un ejemplo con el grado 5.

Deje $p, v_1, \ldots, v_5$ ser como el anterior, y $w_{ij}$ es adyacente a $v_i$$v_j$$i<j$. Añadir en los bordes $[w_{ij}, w_{kl}]$$k>i, k\neq j, l\neq j$.

Cada vértice tiene grado 5, no conectado vértices compartir un vecino, y aparentemente la última condición se cumple así?

edit 2: es un pequeño ejercicio para ver que falla con $\deg(p) =3$ o $\deg(p) = 4$.

edit 3: como se indica en la otra respuesta, en el ejemplo de arriba es la de Clebsch gráfico.