Discrete Math Problem Consider the following graph Note that

Discrete Math Problem

Consider the following graph:

Note that the graph has been constructed so that there are no cycles of length three (triangles) or four (quadrilaterals). Note also that the graph has a total of fifteen edges and ten vertices, and every vertex has degree 3.

Now, suppose this graph had a Hamiltonian cycle. That would mean that you could write out a list of ten edges, visiting each vertex exactly once. There would still be five edges in the graph to account for in the graph. Show that if you try to draw those remaining edges, you must end up with either a triangle or quadrilateral, and thus prove (by contradiction) that the graph does not have a Hamiltonian cycle.

Solution