GO Classes DPP | GATE CS | Discrete Mathematics | Graph Theory

Answer 1

I have already written an answer to the same kind of problem please refer to How to check if a graph has Hamiltonian Cycle

Here is the image showing this is a hamiltonian graph

Answer 2

Answer: 0, the graph does not have a Hamiltonian cycle.

• The visual coloring explicitly demonstrates two disjoint sets. Every edge connects a red vertex to a blue vertex. There are zero edges connecting two red nodes or two blue nodes, making it a bipartite graph

• A Hamiltonian cycle must visit every vertex exactly once and return to the starting vertex. In a bipartite graph, the path must strictly alternate between the two sets (e.g., Red $\rightarrow$ Blue $\rightarrow$ Red $\rightarrow$ Blue). To close the loop without skipping any nodes or repeating visits, an exactly equal number of red and blue vertices is required.

• Since $6$ Red Vertex $\neq$ $5$ Blue Vertex, an alternating path that attempts to cover all 11 vertices will inevitably begin and end on a red node. Because there are no red-to-red edges to close the loop back to the start, a Hamiltonian cycle is impossible.

• 

Takeaway: A bipartite graph with an odd number of total vertices can never contain a Hamiltonian cycle.