December2015 Cs Q2
0. 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.
- Option : D
- Explanation :
EulerCircuits: An Euler circuit is a circuit that uses every edge of a graph exactly once.
HamiltonCircuit: Hamilton circuit, is a graph cycle (i.e., closed-loop) through a graph that visits each node exactly once
Bipartite Graph: A bipartite graph, also called a bigraph, is a set of graph vertices decomposed into two disjoint sets such that no two graph vertices within the same set are adjacent. A bipartite graph is a special case of a k-partite graph with k=2.
From the above definitions, we can see that (d) is false. So the answer is (D).
