Seja um gráfico simples em vértices sem vértice do grau . Suponha que, para quaisquer dois vértices de , exista um vértice exclusivo adjacente a ambos. É um exercício de A Course in Combinatorics , van Lint e Wilson, para provar que esse gráfico é regular.
Minha pergunta, no entanto, é se gráficos que satisfazem as restrições dadas existem. Ao discutir o exercício original durante uma sessão de solução de problemas, alguém perguntou se poderíamos criar um exemplo de gráfico em que cada par de vértices tem um vizinho comum único e não há vértices globais. Também não conseguimos apresentar um exemplo ou procedimento concreto para a construção, nem estabelecemos uma prova de que nenhum gráfico possui essas propriedades.
Alguma sugestão?
Nota: para provar que esse gráfico é regular, ele se mostra bastante direto, a idéia aproximada é emparelhar os vizinhos de cada par de vértices usando os critérios único-comum-vizinho para estabelecer o fato de que cada par de os vértices têm o mesmo grau e, em seguida, um argumento de transitividade, com a ajuda da restrição de não-global-vértice, nos dá que o gráfico é regular.
fonte