## Sunday, 20 October 2013

### Algorithms (graphs)

34.2-2 (Cormen, Leiserson, Rivest, and Stein, Introdution to Algorithms, 3rd edition)

Prove that if G is an undirected bipartite graph with an odd number of vertices, then G is nonhamiltonian.

Introduction to the problem
A bipartite graph is a graph whose vertices can be divided into two disjoint sets A and B such that every edge connects a vertex in A to one in B, that is, A and B are each independent sets.

Examples of bipartie graphs:

As we can see, in the upper picture the graph with odd number of vertices is nonhamiltonian. The second one is hamiltonian.

Proof
Let G=(AB,E) be a bipartite graph. To be Hamiltonian, a graph G needs to have a Hamilton cycle: that is, one which goes through all the vertices of G. As each edge in G connects a vertex in A with a vertex in B, any cycle alternately passes through a vertex in A then a vertex in B.

There are odd number of vertices, so |A|!= |B|. Suppose, without loss of generality, that |A|>|B| , that is, that there are more vertices in A than in B. Let |A|=m,|B|=n. Suppose G has a Hamilton cycle C.
Let that cycle start at uB. After 2n edges have been traversed, we will have arrived back at u again, and all the vertices of B will have been visited. But there will still be mn vertices in A which have not been visited. Hence G cannot be hamiltonian.

QED