For a given graph G having v vertices and e edges which is connected and has no cycles,...
Optym technical mcq question, verified with a worked answer. Free to practise - no sign-up.
For a given graph G having v vertices and e edges which is connected and has no cycles, which of the following statements is true?
Show answer & explanation
Answer: D. D) v = e+1
A connected graph with no cycles is a tree. Every tree with v vertices has exactly e = v - 1 edges, which rearranges to v = e + 1.
Step-by-step Derivation:
Step 1: By definition, a connected acyclic graph is a tree.
Step 2: A tree on v vertices has e = v - 1 edges.
Step 3: Rearranging gives v = e + 1.