Soit un simple graphe sur sommets sans sommet de degré . Supposons que pour deux sommets de , il existe un sommet unique adjacent à chacun d'eux. Il s'agit d'un exercice de A Course in Combinatorics , van Lint et Wilson, pour prouver qu'un tel graphique est régulier.
Ma question, cependant, est de savoir s'il existe des graphes satisfaisant aux contraintes données. Tout en discutant de l'exercice d'origine lors d'une session de résolution de problèmes, quelqu'un a demandé si nous pouvions trouver un exemple de graphique où chaque paire de sommets a un voisin commun unique, et il n'y a pas de sommets globaux. Nous n'avons pas non plus été en mesure de proposer un exemple ou une procédure concrète de construction, ni de prouver qu'aucun graphique ne possède ces propriétés.
Aucune suggestion?
Remarque: comme pour prouver qu'un tel graphique est régulier, il se révèle assez simple, l'idée approximative est de coupler les voisins de chaque paire de sommets en utilisant les critères de voisin commun unique pour établir le fait que chaque paire de les sommets ont le même degré, puis un argument de transitivité, à l'aide de la contrainte no-global-vertex, nous donne que le graphique est régulier.
la source