Demostración - Mismos Conocidos

Demostración de que en todo grupo de dos o más personas existen siempre dos personas que tienen exactamente el mismo número de conocidos en el grupo.

Asumimos que:

• nadie del grupo se conoce a sí mismo;

• nadie del grupo conoce a una persona más de una vez;

• nadie del grupo conoce a una persona sin que esa persona lo conozca.

Podemos representar entonces el grupo de personas como un grafo simple G = (V, E) donde:

• V = personas en el grupo y |V| = n ≥ 2

• E = (u, v) : u conoce a v con u, v ∈ V y |E| = m

Es decir, quiero ver que en un grafo simple de dos o más vértices, dos de ellos tienen el mismo grado.

Sea d la función que asigna a cada vértice de V su número de vecinos:

d : V(G) → ℕ₀

v ↦ |N(v)|

Si alguien no conoce a nadie es claro que nadie puede conocer a todos.

Esto es, ∃ v ∈ V : d(v) = 0 ⇒ ∄ u ∈ V : d(u) = n − 1.

Luego, tenemos que Im(d) ⊈ {0, ..., n − 1} y de aquí |Im(d)| ≤ n − 1.

Como |Dom(d)| = |V| = n tenemos que d no puede ser biyectiva por el principio del palomar.

Luego existen u, v ∈ V distintos tal que d(u) = d(v).

Por lo tanto en un grupo de dos o más personas existen siempre dos personas que tienen exactamente el mismo número de conocidos en el grupo.

◼