Which of the following statement(s) is/are false? (a) A connected multigraph…
2015
Which of the following statement(s) is/are false?
(a) A connected multigraph has an Euler Circuit if and only if each of its vertices has even degree.
(b) A connected multigraph has an Euler Path but not an Euler Circuit if and only if it has exactly two vertices of odd degree.
(c) A complete graph (Kn) has a Hamilton Circuit whenever n ≥ 3.
(d) A cycle over six vertices (C6) is not a bipartite graph but a complete graph over 3 vertices is bipartite.
Codes :
- A.
(a) only
- B.
(b) and (c)
- C.
(c) only
- D.
(d) only
Attempted by 128 students.
Show answer & explanation
Correct answer: D
Final answer: Only statement (d) is false.
Reasoning:
Statement (a) — true: In a connected multigraph, an Euler circuit exists if and only if every vertex has even degree. This is the standard Euler criterion (multiple edges are allowed and loops contribute degree 2).
Statement (b) — true: A connected multigraph has an Euler path but not an Euler circuit exactly when it has precisely two vertices of odd degree; this is the Euler trail criterion.
Statement (c) — true: Every complete graph on n ≥ 3 vertices contains a Hamiltonian circuit (one can visit the vertices in any sequence and return to the start).
Statement (d) — false: The cycle on six vertices is bipartite because cycles of even length are bipartite (vertices alternate between the two partite sets). The complete graph on three vertices is a 3-cycle (triangle), which is not bipartite because it has odd length; hence the claim in (d) is incorrect.
Conclusion: Only statement (d) is false; statements (a), (b), and (c) are true.