Hamilton & Euler Circuits???

Question

Does the graph K2,5 have an Euler circuit? If not, does it have an Euler path? Does the graph K2,5 have a Hamilton path?

Answer 1

K2,5 refers to a complete bipartite graph in which one part consists of 2 vertices while the other part consists of 5 vertices.  "In the mathematical field of graph theory, an Eulerian path is a path in a graph which visits each edge exactly once. Similarly, an Eulerian circuit is an Eulerian path which starts and ends on the same vertex.  A Hamiltonian path is a path in an undirected graph which visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle in an undirected graph which visits each vertex exactly once and also returns to the starting vertex."

A simple negative test for Euler circuits for this type of graph is if any of the vertices are of odd degree.  Since each of the vertices on the part of the graph with 2 vertices are of odd degree, then this graph cannot have an Euler circuit.  

An Euler path is simpler than a Euler circuit since the start and end vertices of the path don't need to be the same.  In the case of this particular graph all the vertices must be of even degree except for two.  Indeed K2,5 does satisfy this rule hence it has a Euler path.  (you can test this by starting your path at one of vertices on the 2 vertex part and trace different edges and you will find all edges covered exactly once and ending on the other vertex on the 2 vertex part).

"No property is known to efficiently verify existence of a Hamilton cycle/path for general graphs."  In this case though K2,5 does not have a Hamilton path since there is no way to visit all of the vertices only once during its traversal.

Answer 2

Think of the degrees of each vertex.

There are:

2 vertices of degree 5

5 vertices of degree 2

However, there is a well known theorem stating that to have an Eulerian circuit, a graph must have ALL EVEN degrees. Two of these are odd, which means there is no Eulerian circuit.

Why does it have to be that way? Well, in order to move through a vertex, you have to come in on an unused edge, and leave on an unused edge. You can't repeat edges! So every time you come to a vertex, you establish TWO edges on it. That means it has even degree.

That same theorem tells us that for Eulerian paths, only the beginning and ending points can have odd degree. That means to have an Eulerian path, all but two of the vertices must have even degrees. That means that this is possible. Based on this, we have to start and end on the part with two vertices (on top in this picture).

http://math.colgate.edu/~kellen/interspa...

So in summary:

Eulerian circuit? No.

Eulerian path? Yes.

A Hamiltonian path does not exist on most complete bipartite graphs. Why? Because you have to go back and forth between sides. For example, let's call the vertices on one side A,B,C,D,E. The other side can be X,Y.

You have to eliminate them one-by-one, but you must alternate from side-to-side. So start with A, then X, then B, then Y, then C... and you're stuck. You can't get to D or E because you need to go through X or Y to do so.

The graph K(m,n) has a Hamiltonian path if and only if |m-n|<3.