Olimpíadas ⇒ Teoria dos Grafos

[goncalves3718]

Em um grupo de [tex3]n[/tex3] pessoas sabe-se que se duas possuem mesmo número de amigos, então elas não possuem amigos em comum. Prove que existe uma pessoa com exatamente um amigo.

[leozitz]

a ideia da solução veio do seguinte
se A e B tem amigos em comum então eles tem um número diferente de amigos
com isso olhando para um vértice qualquer eu consigo ordenar o grau dos amigos deles

só que com isso, como na imagem eu posso fazer crescer o lado esquerdo da desigualdade e se o grau de F for pequeno eu consigo criar uma contradição, ou ainda se tiver muitos amigos (ali usei A, B, C, D, E, F) eu consigo crescer muito e gerar uma contradição também.
(obs: usei |A| pra falar do grau de A, é uma notação creio eu incorreta mas é só pra facilitar a escrita).

sendo assim, seja M o vértice com maior grau, ele tem |M| amigos

supondo que todo mundo tem grau maior que 1 podemos escrever
[tex3]1 < |n_1| < |n_2|<\cdots<|n_{|M|}|\le|M|[/tex3]
a desigualdade [tex3]|n_{|M|}|\le|M|[/tex3] veio do fato de M ter a maior quantidade de amigos
com isso é facil ver que [tex3]|n_i|\ge i+1[/tex3] já que são inteiros
[tex3]|M|+1\le|n_{|M|}|\le|M|[/tex3]
[tex3]|M|+1\le |M|[/tex3]
que é claramente uma contradição