Every graph with n vertices and n-k edges has at least....
- Thread starter hero
- Start date
Suppose you take a graph G and shrink one of its edges down until it disappears and the two vertices at the ends of that edge get merged into a single vertex. The new graph fairly obviously has the same number of components as G, but it has one less vertex and one less edge.
Now if you're given a graph with n vertices and n-k edges, you can carry out this shrinking operation on each of its edges in turn, until you have eliminated all n-k edges. You'll then be left with k vertices and no edges. So each vertex is an isolated component. Since the number of components in the graph has not changed during this sequence of operations, the original graph must also have had k components.
So why did the question say that the graph must have at least k components, when the above argument seems to show that it must have exactly k components? The only answer I can see to that is that the question must have allowed the possibility of a graph with loops: if an edge connects a vertex to itself then when you shrink the edge down to length zero, you lose an edge but not a vertex. That means that when you have shrunk all n-k edges to length zero, there may be more than k remaining vertices.
Edit In fact, you certainly have to allow for multiple edges and loops, even if the original graph does not contain any. For example, if you shrink an edge whose two vertices are both connected to a third vertex, this will produce a double edge. If you then shrink one of these double edges, it will produce a loop.
Now if you're given a graph with n vertices and n-k edges, you can carry out this shrinking operation on each of its edges in turn, until you have eliminated all n-k edges. You'll then be left with k vertices and no edges. So each vertex is an isolated component. Since the number of components in the graph has not changed during this sequence of operations, the original graph must also have had k components.
So why did the question say that the graph must have at least k components, when the above argument seems to show that it must have exactly k components? The only answer I can see to that is that the question must have allowed the possibility of a graph with loops: if an edge connects a vertex to itself then when you shrink the edge down to length zero, you lose an edge but not a vertex. That means that when you have shrunk all n-k edges to length zero, there may be more than k remaining vertices.
Edit In fact, you certainly have to allow for multiple edges and loops, even if the original graph does not contain any. For example, if you shrink an edge whose two vertices are both connected to a third vertex, this will produce a double edge. If you then shrink one of these double edges, it will produce a loop.
