El gráfico sin triángulos es regular

Question

Supongamos que $G$ es un triángulo simple $n$ gráfico de vértices tal que cada par de vértices no adyacentes tiene exactamente $2$ vecinos en común.

$1>$ Demostrar que $G$ es regular (Un gráfico es regular si los grados de todos sus vértices son iguales)

$2>$ Dado que $G$ es regular de grado $k$ demostrar que el número de vértices del grafo $G$ es $1+{k+1\choose 2}$

¿Puede alguien ayudarme a empezar?

Answer 1

1) Supongamos $A$ y $B$ están conectados por el borde, $C_1, C_2,\cdots, C_l$ son vecinos de $A$ que no son $B$ ; $D_1, D_2,\cdots, D_m$ son vecinos de $B$ que no son $A$ . Entonces, veamos lo que nos da la declaración. En primer lugar, ninguno de $C_i$ es vecino de $B$ porque de lo contrario $ABC_i$ es un triángulo de aristas, pero $G$ es libre de triángulos. Del mismo modo, ninguno de $D_j$ es vecino de $A$ .

Veamos ahora cómo $D_j$ y $C_i$ están conectados por las aristas. Para cualquier $i$ los vértices $C_i$ y $B$ no están conectados, por lo que tienen dos vecinos comunes. Uno de ellos es $A$ . El otro debe ser uno de $D_j$ porque son los únicos otros vecinos de $B$ . Así, para cualquier $i$ : $C_i$ está relacionado con $D_j$ para algunos $j$ . Este $j$ es único, en caso contrario $C_i$ y $B$ tienen al menos 3 vecinos comunes, lo que no tiene sentido. Del mismo modo, se puede demostrar que cualquier $D_j$ está conectado con exactamente uno de $C_i$ . Pero todo esto significa que hay el mismo número de $C_i$ y $D_j$ Así que $A$ y $B$ tienen el mismo grado.

Ahora basta con ver que entonces dos vértices cualesquiera tienen el mismo grado. Si dos vértices $A$ y $B$ son adyacentes, acabamos de demostrarlo, y si no, tienen un vecino común $C$ . $\deg A=\deg C=\deg B$ .

2) Para cualquier par de vértices desconectados $(A,B)$ llamemos a un par de sus dos vecinos comunes $(C,D)$ el hermano para $(A,B)$ . $(C,D)$ también están desconectados porque $G$ es libre de triángulos, y su hermano es $(A,B)$ . Así, todos los pares de vértices desconectados se dividen en pares hermanos de pares $((A,B),(C,D))$ . En particular, para cualquier vértice $A$ el número de pares $(C,D)$ formado por sus vecinos (todos están desconectados por la libertad del triángulo), y el número de pares $(A,B)$ , donde $B$ no está relacionado con $A$ son iguales, porque están en correspondencia uno a uno bajo la relación de parentesco. Denotemos ahora el número de vértices por $n$ y escribir esa igualdad: $${k\choose2}=n-k-1$$ De ello se desprende el punto 2).