2
$\begingroup$

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?

$\endgroup$
6
  • 2
    $\begingroup$ Take a star and remove the central vertex. What happens to the number of connected components? $\endgroup$
    – Christoph
    Commented Oct 25, 2015 at 16:37
  • $\begingroup$ @Christoph Yes, The number of connected components will be equal to the number of the remaining vertices right , so if we have $10$ vertices and we removed the central vertex, we would have $9$ vertices with $9$ connected components right ? $\endgroup$
    – alkabary
    Commented Oct 25, 2015 at 16:39
  • $\begingroup$ Indeed, so the number of connected components increases by $\operatorname{deg}(v)-1$ in this case. This should be the worst case. $\endgroup$
    – Christoph
    Commented Oct 25, 2015 at 16:40
  • $\begingroup$ You mean $deg(v)$ not $deg(v)-1$ right !! $\endgroup$
    – alkabary
    Commented Oct 25, 2015 at 16:42
  • 1
    $\begingroup$ No, in your example of $10$ vertices you have $1$ connected component to begin with and end up with $9$, so the increase is $8$ while the central vertex had degree $9$. — If you solved the first problem you can bound the second by removing the edges adjoint to your vertex step by step and then finally removing the vertex itself (getting rid of one component). $\endgroup$
    – Christoph
    Commented Oct 25, 2015 at 16:43

2 Answers 2

Reset to default
3
$\begingroup$

When removing an edge $e=(v,w)$ of your graph there are two cases:

  1. 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.

  2. 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$.

$\endgroup$
1
  • $\begingroup$ How would you show that in case $2$ all other components will be fixed and that the path component containing $v$ and $w$ is split into exactly two components, I have tried a lot, But I couldn't do it $\endgroup$
    – alkabary
    Commented Oct 31, 2015 at 6:09
0
$\begingroup$

So, seems to me that quite simply an edge joining precisely two points and for components to be disconnected they cannot share a point in common...

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .