Školjka

Dokažimo da je $n$ nužno oblika $3k+1$. \\ Promotrimo proizvoljan čvor $A$. Čvorove povezane s $A$ zvat ćemo \emph{susjedi} od $A$, a čvorove koji nisu povezani s $A$ zvat ćemo \emph{nesusjedi} od $A$. Vezice patika ćemo zvati \emph{graf}. \\ Promotrimo skup svih susjeda od $A$. $A$ ima barem jednog susjeda jer svaka $2$ čvora imaju barem jednog zajedničkog susjeda. Svaki čvor koji je susjed od $A$ mora biti povezan s još točno $2$ susjeda od $A$ zbog prvog uvjeta zadatka. \\ Pretpostavimo da je neki od tih susjeda $B$ te da je povezan sa susjedima $C$ i $D$. Tada $C$ i $D$ imaju $2$ zajednička susjeda ($A$ i $B$) pa su i oni nužno povezani. Zaključujemo da su susjedi od $A$ podijeljeni u disjunktne tročlane skupove, pa je broj susjeda od $A$ djeljiv s $3$. \\ Ako $A$ nema nesusjeda, nema se što dokazivati. U suprotnom, svaki nesusjed od $A$ je spojen s točno jednim susjedom od $A$ zbog drugog uvjeta zadatka. Zbog toga možemo skup nesusjeda particionirati po tome s kojim su susjedom povezani. \\ Pretpostavimo da je neki susjed $E$ spojen s nesusjedima $Q_1,Q_2,\ldots,Q_d.$ \\ Tada $E$ i $Q_i$ za svaki $i\in \{1,\ldots,d\}$ imaju još točno $2$ zajednička susjeda koji su ujedno i nesusjedi od $A$. Neka je neki $Q_i$ spojen s $Q_j$ i $Q_k$. Tada $Q_j$ i $Q_k$ imaju $2$ zajednička susjeda pa su nužno povezani. Vidimo da su $Q_1,Q_2,\ldots,Q_d$ podijeljeni u disjunktne trojke, pa je $d$ nužno djeljiv s $3$. Iz toga slijedi da je i broj nesusjeda nužno djeljiv s $3$. \\ Dokažimo sada da za svaki $n$ oblika $3k+1$ postoji graf s traženim svojstvima. Označimo vrhove s $Q_0,Q_1,\ldots,Q_{3k}$. Povežimo $Q_0$ sa svim ostalim čvorovima te povežimo za svaki $i\in \{1,\dots,k\}$ čvorove $Q_{3i-2},Q_{3i-1}$ i $Q_{3i}$ svaki sa svakim. Svaki taj tročlani skup zovimo \emph{grupica}. \\ $Q_0$ ima $2$ zajednička susjeda sa svakim od preostalih. Dva člana iste grupice imaju točno $2$ zajednička susjeda ($Q_0$ i preostali član grupice). Dva člana različitih grupica imaju točno jednog zajedničkog susjeda, $Q_0$. Dakle, konstrukcija je valjana.