Konstruksi grafik di mana setiap pasangan simpul memiliki tetangga bersama yang unik

Misalkan menjadi grafik sederhana pada n simpul ( n > 3 ) tanpa simpul derajat n - 1 . Misalkan untuk setiap dua simpul G , ada simpul unik yang berdekatan dengan keduanya. Ini adalah latihan dari A Course in Combinatorics , van Lint dan Wilson, untuk membuktikan bahwa grafik seperti itu teratur.$G$$n$$(n > 3)$$n − 1$$G$

Namun, pertanyaan saya adalah apakah grafik yang memenuhi batasan yang diberikan bahkan ada. Saat mendiskusikan latihan asli selama sesi pemecahan masalah, seseorang bertanya apakah kita bisa membuat contoh grafik di mana setiap pasangan simpul memiliki tetangga bersama yang unik, dan tidak ada simpul global. Kami juga tidak dapat menemukan contoh konkret atau prosedur untuk konstruksi, kami juga tidak membuat bukti bahwa tidak ada grafik yang memiliki properti ini.

Ada saran?

Catatan: untuk membuktikan bahwa grafik seperti itu teratur, ternyata cukup mudah, ide kasarnya adalah memasangkan tetangga dari setiap pasangan simpul menggunakan kriteria unik-umum-tetangga untuk menetapkan fakta bahwa setiap pasangan simpul memiliki derajat yang sama, dan kemudian argumen transitivitas, dengan bantuan batasan no-global-vertex, memberi kita bahwa grafiknya teratur.

Jika Anda menyingkirkan kondisi "tidak ada simpul derajat ", grafik dengan properti yang setiap dua simpul memiliki tepat satu tetangga yang sama persis adalah grafik persahabatan (seperangkat segitiga yang direkatkan bersama pada simpul umum); seperti yang dijelaskan oleh artikel tertaut, ini adalah teorema Erd, Rényi, dan Sós. Namun yang jelas, semua grafik tersebut memiliki simpul derajat n - 1 ; satu-satunya yang biasa adalah segitiga. Jadi jawaban untuk pertanyaan Anda adalah bahwa, tidak, grafik dengan properti tetangga yang sama dan tanpa derajat - n - 1 tidak ada.$n-1$$n-1$$n-1$