If we have a graph $G$ and $e$ is an edge in this graph. Now I want to
show that $G − e$ has at most one more connected component than G.Now
if we remove one vertex from G, by how much can the number of
connected components can increase?
I think we would have two cases if we remove an edge from a graph.
(case 1) The graph is still connected, Meaning that every vertex has a path to every other vertex, in this case, The connected components are still the same. (Here the degree of the vertex is more than $1$ because the vertex is still connected to the graph , right ?)
(case 2) The vertex has only this edge (Degree =1) and so the graph becomes disconnected, But I have a hard time arguing that it has at most one more connected component.
Now, if we remove a vertex, this means that we remove all edges connected to this vertex, I did this for $k_3$ , $k_4$ to get sense of it, and still the connected components only increase by $1$, is that true and how can I argue here ?
Best Answer
When removing an edge $e=(v,w)$ of your graph there are two cases:
There exists a cycle involving $e$. In this case the cycle minus $e$ is still a path between $v$ and $w$, so any two vertices connected by a path prior to removing $e$ are still connected by a path. The number of connected components doesn't change.
There exists no cycle involving $e$, so $e$ is the only path connecting $v$ and $w$. Hence, $v$ and $w$ are now in two disjoint path components. Show that the path component containing $v$ and $w$ is split into exactly two components, while all other components stay fixed.
Having dealt with edge removal you can consider vertex removal the following way: Let $v$ be a vertex with degree $\operatorname{deg}(v)$. First remove the $\deg(v)$ edges adjacent to $v$. By the previous argument the number of connected components increases by at most $\deg(v)$. Now remove $v$ itself, which is in a connected component of its own by now, so the number of connected components decreases by $1$ when removing $v$.