Show that $G=(V,E)$ with $|V| \geq 4$ and the property that for any three vertices, at least two edges are in $E$ is Hamiltonian

Question

I can't solve the following combinatorics problem

Let $G=(V,E)$ be a graph with $|V|\geq4$ and with the property that for any three of its vertices $u$, $v$ and $w$,at least two of edges $uv$, $uw$ and $vw$ are in $E$. Show that $G$ is Hamiltonian.

Answer 1

Assume we have a graph with the above properties. We use a result of Dirac stating for a graph with $n \geq 3$ vertices and the degree of each vertex is at least $n/2$ then the graph is Hamiltonian. Let $u$ be a vertex of G. When $n=4$, name the other vertices $v_1, v_2, v_3$. For the triplet of vertices $(u, v_1, v_2)$ assume $uv_1$ is an edge. Then for the triplet $(u, v_2, v_3)$ either $uv_2$ or $uv_3$ is an edge thus $u$ has at least degree 2 and Dirac's theorem is satisfied. Likewise when $n=5$ each vertex is guaranteed two have 3 edges. For $n \geq 6$ it is more simple. There are $n-3$ triplets whose intersection is only $u$ thus $u$ has at least degree $n-3 > n/2$. Hence for a graph, G, with $n \geq 4$ vertices and the prescribed edge condition we have shown G is Hamiltonian.

Answer 2

We can prove by induction, base case are $4$ and $5$ vertices cases. They can be brute forced so I will leave it to you.

Assume the statement works for $n-2$ vertices and we look at the case for $n$ vertices.

(1) If it is a complete graph then obviously it has a Hamilton cycle.

(2) If it is not a complete graph then there exist vertices $u,v$ that are not connected. Take $u,v$ out and the remaining graph still has the property that every three vertices has two pair connected becase taking out another vertex won't affect the three vertices. Now the remaining graph has a Hamilton Cycle by induction hypothesis, say it is $a_1a_2a_3...a_{n-2}$.

Add $u,v$ back, since $uv$ is not connected, both of them are connected to all $a_1,a_2,...,a_n$. Now our new Hailton cycle would be $a_1a_2...a_{n-4}ua_{n-3}va_{n-2}$.