Answer to Question #23188 in Discrete Mathematics for Sujata Roy

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
1
Expert's answer
2019-07-24T10:22:36-0400

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.







Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Comments

Nwankwo Gabriel
21.07.19, 21:48

D

Leave a comment

LATEST TUTORIALS
New on Blog
APPROVED BY CLIENTS