Skip to content
Quantoros

A graph has n vertices and n-1 edges. Must it be a tree? Give a counterexample and one extra assumption that fixes the…

Quant ResearchLevel: FoundationNecessary not sufficient

A graph has n vertices and n-1 edges. Must it be a tree? Give a counterexample and one extra assumption that fixes the statement.

Hints
  • Try putting a cycle in one component.
  • The edge-count criterion needs a structural assumption.

Answer

No: a triangle plus an isolated vertex has 4 vertices and 3 edges. Adding connectedness makes n-1 edges sufficient for a tree; alternatively acyclicity plus the count forces one component.

Source and licence: Oscar Levin — Discrete Mathematics: An Open Introduction, 3rd edition · CC-BY-SA-4.0 · answer: Quantoros editorial

Related questions