Question

For a connected, undirected graph G=( V, E ), which of the following must be true?
I. ∑v ∈V
degree(v) is even.
II. E ≥ |V|− 1
III. G has at least one vertex with degree 1.
(A) I only
(B) II only
(C) III only
(D) I and II
(E) II and III

Answer 1

The first statement is true from handshaking lemma. The second one is true from being famous connected. The connected graph with smallest amount of edges is always a tree, so according to the tree definition |V| - 1 = |E|. In case we add cycles to our tree |V| - 1 <= |E|. The third statement is wrong for connected graphs, counterexample is G ({v1}, {}). Correct answer is D.