10
$\begingroup$

enter image description here

I know that a Hamiltonian graph has a path that visits each vertex once. But I am not sure how to figure out if this one does. Obviously I can try and trace various different paths to see if one works but that is incredibly unreliable.

So my question is, if this graph is Hamiltonian, where would the Hamilton cycle be? And if it is not Hamiltonian, how can we prove it?

Thank you!

$\endgroup$
  • 6
    $\begingroup$ A Hamiltonian graph is one which has a Hamiltonian cycle. So it's not enough to have a Hamiltonian path (which the graph has). Source: mathworld.wolfram.com/HamiltonianGraph.html $\endgroup$ – GregT Nov 20 '17 at 9:34
  • $\begingroup$ @corsiKa : You are describing an Eulerian path or cycle (visits every edge), not a Hamiltonian path or cycle (visits every vertex). $\endgroup$ – Eric Towers Nov 21 '17 at 2:56
12
$\begingroup$

A more verbose explanation of the argument made by Lord Shark the Unknown's answer:

This is a bipartite graph (two sets of vertices that form a graph such that no edge places two vertices from the same set adjacent). Colour the three middle vertices red and the other four vertices blue (indicating the two sets).

Every edge in the graph connects a red and a blue vertex. Therefore every path in the graph will visit vertices alternating in color.

Since any cycle has to end on the same vertex as it started, the path has to visit an even number of vertices. Otherwise the path would require connecting a red to a red vertex or a blue to a blue vertex, which we know we cannot do since this is a bipartite graph. This means every cycle will contain an equal amount of red and blue vertices.

Since any Hamiltonian cycle has to contain all vertices and this graph does not have an equal amount of red and blue vertices, it is impossible in this graph to create a Hamiltonian cycle.

Note that the argument does not work the other way around; bipartite graphs exist with equal amounts of points in both sets where Hamiltonian cycles are not possible. Imagine a graph like the one provided in the question, but with four groups of vertices: 2 (red) - 1 (blue) - 1 (red) - 2 (blue). Here it is impossible to create a Hamiltonian cycle since it would require crossing the middle vertices twice.

$\endgroup$
  • 2
    $\begingroup$ It should be noted that the real problem here is an independent set that is strictly larger than its neighborhood. The unbalanced bipartite graph is just an instantiation of this problem with the independent set being the larger part. $\endgroup$ – Bob Krueger Nov 21 '17 at 2:51
42
$\begingroup$

This is a bipartite graph. Colour the three middle vertices red and the other four vertices blue. Each path in the graph has vertices alternating in colour. So any Hamiltonian cycle has an equal number of red and blue vertices...

$\endgroup$
  • 2
    $\begingroup$ So you are saying that it's not Hamiltonian, as it's impossible to find a Hamiltonian cycle in a bipartite graph when the two parts have different number of vertices. $\endgroup$ – GregT Nov 20 '17 at 15:48
1
$\begingroup$

One can never trace a Hamiltonian cycle in a graph with vertices having odd egde number. One can never find a Hamiltonian path in a graph with more than two vertices having odd egde number.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.