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=(A∣B,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

u∈B. 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

m−n vertices in

A which have not been visited. Hence

G cannot be hamiltonian.

QED

## No comments:

## Post a Comment