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:
There are odd number of vertices, so |A|!= |B|. Suppose, without loss of generality, that
Let that cycle start at