Konstrukcja wykresów, w których każda para wierzchołków ma unikalnego wspólnego sąsiada

Niech będzie prostym wykresem na wierzchołkach bez wierzchołka stopnia . Załóżmy, że dla dowolnych dwóch wierzchołków istnieje unikalny wierzchołek przylegający do nich obu. Jest to ćwiczenie z Kursu kombinatoryki van Linta i Wilsona, aby udowodnić, że taki wykres jest regularny.$G$$n$$(n > 3)$$n − 1$$G$

Moje pytanie brzmi jednak, czy w ogóle istnieją wykresy spełniające podane ograniczenia. Omawiając oryginalne ćwiczenie podczas sesji rozwiązywania problemów, ktoś zapytał, czy możemy wymyślić przykład wykresu, na którym każda para wierzchołków ma unikalnego wspólnego sąsiada i nie ma wierzchołków globalnych. Nie byliśmy w stanie wymyślić konkretnego przykładu ani procedury konstrukcyjnej, ani też nie udowodniliśmy, że żaden wykres nie ma tych właściwości.

Jakieś sugestie?

Uwaga: jeśli chodzi o udowodnienie, że taki wykres jest regularny, okazuje się, że jest dość prosty, szorstki pomysł polega na parowaniu sąsiadów każdej pary wierzchołków przy użyciu kryteriów unikatowy wspólny sąsiad, aby ustalić, że każda para wierzchołki mają ten sam stopień, a następnie argument przechodniości, za pomocą ograniczenia no-global-vertex, daje nam regularność wykresu.

Jeśli pozbędziesz się warunku „brak wierzchołka stopnia ”, wykresy z właściwością, że co dwa wierzchołki mają dokładnie jednego wspólnego sąsiada, są dokładnie wykresami przyjaźni (zestaw trójkątów sklejonych razem we wspólnym wierzchołku); jak opisano w powiązanym artykule, jest to twierdzenie Erdősa, Rényiego i Sósa. Ale oczywiście wszystkie takie wykresy mają wierzchołek stopnia ; jedynym regularnym jest trójkąt. Zatem odpowiedź na twoje pytanie brzmi: nie, nie istnieje wykres ze wspólną właściwością sąsiada i bez wierzchołka stopnia .$n-1$$n-1$$n-1$