|
Post by vsiap on Nov 26, 2014 3:54:38 GMT
We use induction on the number of edges. Let P (n) be the proposition that every connected graph with n vertices has at least n-1 edges.
Base case: A graph with a single vertex clearly has at least 0=1-1 edges.
Inductive step: Let n be a positive integer and suppose any connected graph with k vertices has at least k − 1 edges for any integer k with 1 ≤ k ≤ n.
Let G be a connected graph with n + 1 vertices and let v be a vertex of G. Remove v and all incident edges to v from G. The resulting graph, which we will call G′, may or may not be connected, but we do know it has n vertices. Suppose G′ has s components where 1 ≤ s ≤ n. Each component is a connected graph with n or fewer vertices, so we may apply the inductive step to each component. For each component, if the component has k vertices then it has at least k − 1 edges. Thus G′ must have at least n − s edges. When v was removed from G we only removed edges incident to v to obtain G′. For each component in G′ there must be an edge from v to a vertex in that component since G was connected. Thus there must be at least s more edges in G than there are in G′, i.e. the number of edges in G is at least (n−s)+s = n.
|
|