En un grupo de personas$n$, todos los que tienen un amigo en común conocen un número diferente de personas. ¿Existe alguien que conozca solo una persona?

Question

En un grupo de n personas ($n \geq 2$) al menos dos personas se conocen entre sí. Se supone que si dos personas tienen un amigo en común, saben número diferente de personas. Demostrar que en este grupo existe una persona que sólo conoce una persona.

Mi planteamiento es el siguiente: Deje $G=(V,E)$ ser un grafo tal que $|V(G)|=n$. Asumir el contrario, que el $deg(v)\geq 2$, para todos los $v \in V(G)$. Al menos dos personas se conozcan unos a otros así que vamos a $v,w \in V(G)$ ser tal que $(v,w) \in E(G)$. Pero, a partir de la suposición de $deg(v),deg(w)\neq 1$, por lo que hay al menos una persona $s\in V(G)$ tal que $v,w,s$ formar un ciclo. Pero, a continuación, todos ellos tienen un amigo en común, por lo que todos sabemos número diferente de personas.

Pero sé que yo estoy atascado y no sabes cómo terminar el argumento.

Answer 1

Que $v$ sea un vértice con el más alto grado de $k\geq 1$ $G$. Que $v_1,\ldots, v_k$ sea los vértices conectados a $v$. Desde $v_i$ y $v_j$ tienen un vecino común, tenemos $\deg v_i \neq \deg v_j$ % todos $i\neq j$. $1 \leq \deg v_i \leq k$ % Todo $i$y si son todos distintos, uno debe tener $\deg v_i =1$ $i$.