Question #23188
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
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
Expert's answer
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.
