Finite Connected Simple Graph is Tree iff Size is One Less than Order/Sufficient Condition
Jump to navigation
Jump to search
Theorem
Let $T$ be a finite connected simple graph of order $n$.
Let the size of $T$ be $n - 1$.
Then $T$ is a (finite) tree.
Proof
Let $T$ is a connected simple graph of order $n$ with size $n - 1$.
From Finite Connected Simple Graph with Size One Less than Order has no Circuits:
- $T$ has no circuits.
Hence $T$ is a tree by definition.
$\blacksquare$
Sources
- 1977: Gary Chartrand: Introductory Graph Theory ... (previous) ... (next): $\S 4.1$: The Minimal Connector Problem: An Introduction to Trees: Problem $9$
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous): $\S 2.3.4.1$: Free Trees: Theorem $\mathrm A$