Bau von Graphen, in denen jedes Paar von Eckpunkten eines einzigartigen gemeinsamen Nachbarn haben

Lassen Sie ein einfacher Graph auf seine n Ecken ( n > 3 ) ohne Ecke vom Grad n - 1 . Nehmen wir an, dass für je zwei Ecken von G , gibt es eine einzigartige Eckpunkt benachbart zu beiden. Es ist eine Übung von A Course in Kombinatorik , van Lint und Wilson, zu beweisen , dass ein solcher Graph regulär.$G$$n$$(n > 3)$$n − 1$$G$

Meine Frage ist jedoch, ob Diagramme, die die gegebenen Randbedingungen erfüllt, sogar existieren. Während der Besprechung der ursprünglichen Übung während einer Problemlösungssitzung fragte jemand, ob wir ein Beispiel für ein Diagramm finden könnten, in dem jedes Eckpunktpaar einen eindeutigen gemeinsamen Nachbarn hat und es keine globalen Eckpunkte gibt. Weder konnten wir ein konkretes Beispiel oder ein konkretes Konstruktionsverfahren finden, noch haben wir den Beweis erbracht, dass kein Graph diese Eigenschaften hat.

Irgendwelche Vorschläge?

Hinweis: Um zu beweisen, dass ein solches Diagramm regelmäßig ist, stellt sich heraus, dass es ziemlich einfach ist. Die grobe Idee besteht darin, die Nachbarn jedes Scheitelpunktpaares unter Verwendung der Unique-Common-Neighbor-Kriterien zu paaren, um die Tatsache zu ermitteln, dass jedes Paar von Ecken den gleichen Grad haben, und dann ein transitivity Argument, mit Hilfe der nicht-global-Vertex-Einschränkung, gibt uns, dass der graph regulär.

Wenn Sie von der loszuwerden „keine Ecke vom Grad “ Zustand, die Graphen mit der Eigenschaft , dass je zwei Ecken genau ein gemeinsamer Nachbar ist genau die Freundschaft Graphen (ein Satz von Dreiecken zusammengeklebt an einem gemeinsamen Scheitelpunkt); Wie der verlinkte Artikel beschreibt, ist dies ein Satz von Erdős, Rényi und Sós. Aber offensichtlich haben alle diese Graphen einen Scheitelpunkt vom Grad n - 1 ; die einzige regelmäßige eine ist ein Dreieck. Die Antwort auf Ihre Frage lautet also, dass es kein Diagramm mit der gemeinsamen Nachbarkennzahl und ohne einen Vertex mit dem Grad n - 1 gibt.$n-1$$n-1$$n-1$