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

Question

Which of the following statements concerning $K_n - $ (a complete graph on $n$ vertices) is/are TRUE? (Mark all the appropriate choices)

• A. $K_5$ contains an Euler circuit
• B. $K_4$ contains an Euler circuit
• C. $K_4$ contains a Hamiltonian cycle
• D. $K_5$ contains a Hamiltonian cycle

Answer 1

A graph has an Euler circuit if and only if all of its degrees are even. When  $n$  is odd,  $K_n$  contains an Euler circuit. This is because every vertex has degree  $n-1,$  so an odd  $n$  results in all degrees being even.

For all values of $n,$ $K_n$ contains $(C_n)$ as a subgroup, which is a cycle that includes every vertex exactly once and hence is a Hamiltonian cycle.