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

To prove that if $G$ is an undirected bipartite graph with an odd number of vertices, then $G$ is nonhamiltonian, we can proceed as follows:

1. Definition of Bipartite Graph: Recall that a bipartite graph $G$ can be divided into two disjoint sets of vertices, say $U$ and $V$, such that every edge in $G$ connects a vertex in $U$ to a vertex in $V$. There are no edges within $U$ or within $V$.

2. Hamiltonian Cycle: A Hamiltonian cycle in a graph is a cycle that visits every vertex exactly once and returns to the starting vertex.

3. Vertex Count in Bipartite Graph: Let $|U|$ be the number of vertices in set $U$ and $|V|$ be the number of vertices in set $V$. Since $G$ is bipartite, the total number of vertices $|U| + |V|$ must be the total number of vertices in $G$.

4. Odd Number of Vertices: Given that $G$ has an odd number of vertices, we can write $|U| + |V| = 2k + 1$ for some integer $k$. This implies that the sum of the vertices in $U$ and $V$ is odd.

5. Hamiltonian Cycle in Bipartite Graph: For $G$ to have a Hamiltonian cycle, the cycle must alternate between vertices in $U$ and vertices in $V$. This means that the cycle must visit an equal number of vertices in $U$ and $V$ because each step in the cycle moves from one set to the other.

6. Contradiction: However, since $|U| + |V|$ is odd, it is impossible to split the vertices into two equal parts. Specifically, if $|U| + |V| = 2k + 1$, then one of $|U|$ or $|V|$ must be $k$ and the other must be $k + 1$. This imbalance means that it is impossible to alternate between $U$ and $V$ an equal number of times, which is required for a Hamiltonian cycle.

7. Conclusion: Therefore, it is impossible for $G$ to have a Hamiltonian cycle. Hence, $G$ is nonhamiltonian.

This completes the proof that if $G$ is an undirected bipartite graph with an odd number of vertices, then $G$ is nonhamiltonian.