Consider what a hamiltonian cycle in \(\bfG_{4}\) would look like. The graph has \(15\) edges, and a hamiltonian cycle would use \(10\) of them. Thus, you’d have the cycle and five leftover edges that would connect vertices across the cycle (“chords”). How would these edges fit along the cycle? If an edge connected a vertex to a vertex two steps down the cycle (for example, if the cycle contains the sequence \(a,b,c\) of vertices and there’s an edge from \(a\) to \(c\)), then there would be a triangle (a cyle on three vertices) in the graph. There is no such cycle in \(\bfG_{4}\text{.}\) If a chord connects a vertex to another vertex at distance three along the hamiltonian cycle, then there is a cycle on four vertices. However, there is no such cycle in \(\bfG_{4}\text{.}\)
Now suppose that a chord connects a vertex \(v_{0}\) to another vertex \(v_{1}\) at distance four along the hamiltonian cycle. Let \(v_{0}'\) be the vertex opposite \(v_{0}\) along the hamiltonian cycle. There is also a chord incident with \(v_{0}'\text{,}\) connecting it across the hamiltonian cycle to a vertex \(v_{1}'\text{.}\) We’ve already explained that the distance from \(v_{0}'\) to \(v_{1}'\) along the hamiltonian cycle cannot be less than four, and it cannot be five since that would give \(v_{0}'\) degree four. Thus the distance along the hamiltonian cycle from \(v_{0}'\) to \(v_{1}'\) must be four. Now \(v_{0},v_{1},v_{1}',v_{0}'\) is a cycle of length four (draw a picture to convince yourself), which we don’t have in \(\bfG_{4}\text{.}\) Finally, the only option that remains is that the chords all connect vertices that are exactly opposite each other on the hamiltonian cycle. However, then if \(v_{0}\) and \(v_{1}\) are adjacent along the hamiltonian cycle and \(v_{0}'\) and \(v_{1}'\) are the vertices opposite them, \(v_{0},v_{1},v_{1}',v_{0}'\) is a cycle of length four.
