GATE Overflow Test Series | Discrete Mathematics | Test 4 | Question: 14

Question

Which of the following statements concerning $K_{m,n} - $ (a complete bipartite graph of partition sizes $m$ and $n)$ is/are TRUE? (Mark all the appropriate choices)

• A. $K_{4,4}$ contains an Euler circuit
• B. $K_{5,2}$ contains an Euler path
• C. $K_{5,5}$ contains a Hamiltonian cycle
• D. $K_{5,4}$ contains a Hamiltonian path

Answer 1

A graph has an Euler circuit if and only if all of its degrees are even.

If both  $m$  and  $n$  are even, then  $K_{m,n}$  has an Euler circuit. When both are odd, there is no Euler path or circuit. If one is $2$ and the other is odd, then there is an Euler path but not an Euler circuit. So, options A and B are TRUE.

Every cycle in a bipartite graph is even and alternates between vertices from $V_1$ and $V_2.$ Since a Hamilton cycle uses all the vertices in $V_1$ and $V_2,$ we must have $m  = n.$

As long as  $|m-n|\leq 1,$  the graph  $K_{m,n}$  will have a Hamilton path. So, options C,D are also TRUE.

So, all the given options are TRUE here.

Comments

@gatecse For option C, K5,5 is not 2-connected. Can we say that it is not a necessary condition for a graph to be Hamiltonian?