Simple Graph with no Circuits and Size One Less than Order is Connected
Jump to navigation
Jump to search
Theorem
Let $G$ be a simple graph of order $n$ such that $G$ has no circuits.
Let the size of $G$ be $n - 1$.
Then $T$ is connected.
Proof
Aiming for a contradiction, suppose $G$ is not connected.
Then $G$ has at least $2$ components.
By the Pigeonhole Principle, at least one of those components has at least as many edges as vertices.
Hence by Finite Connected Simple Graph is Tree iff Size is One Less than Order, that component is not a tree.
Hence as that component is itself connected but not a tree by definition it has at least one circuit.
But by hypothesis $G$ has no circuits.
The result follows by Proof by Contradiction.
$\blacksquare$