Claim: Every connected graph with $n$ vertices has at least $n - 1$ edges.
Proof by induction:
$P(n)$ = "Every connected graph with $n$ vertices has at least $n - 1$ edges." $\forall n \ge 1$
Base case: A graph with $1$ vertex has $0$ edges.
Inductive step:
Remove a vertex with the lowest degree and all its edges from the connected graph with $n + 1$ vertices.
The resulting graph has $n$ vertices. Apply the inductive hypothesis - this graph has at least $n - 1$ edges.
When you add the removed vertex back, it must connect to at least $1$ vertex in order for the overall graph to be connected.
The graph now contains at least $n - 1 + 1$ or $n$ edges
I'm new to graph theory, so I'm wondering if I completed this induction proof with the right steps. Any other methods or additions to this proof would also be appreciated. Thanks!
No comments:
Post a Comment