1
$\begingroup$

Question

Write the definition of a cut vertex and a cut edge. How many components do you get if you remove a cut edge from a connected graph? What about a cut vertex?

My Solution

A cut-vertex is a vertex which when removed from a graph increases the number of components. A cut-edge is an edge which when removed from a graph increases the number of components.

Problem

I am not able to come up with any exact formula to determine the change in components when removing a cut-vertex from a graph.

Graph 1 Graph 2

From what I can see in the above graphs, removing the rightmost vertex from the first graph leaves you with $3$ components (an increase of $2$), whereas removing the rightmost vertex from the second leaves you with $2$ components (an increase of $1$). As both these vertices have the same degree, I am not sure what other properties to look at to be able to potentially determine the change in components.

I considered that the question may just be asking if there is a net increase or decrease in the number of connected components when a cut-vertex or cut-edge is removed, but that seems too easy since the answer is in their definition.

$\endgroup$

1 Answer 1

2
$\begingroup$

The question is a little vague- for cut-edges, there is a precise answer, namely that the number of components increases by precisely one. This is fairly easy to see- if $e$ is a cut-edge, there will be one component of $G-e$ that contains one endpoint of $e$ and another component that contains the other end point. These are different components since $e$ is a cut-edge, and adding $e$ makes them into one component.

However, as you've already shown, you can't nail this down to an exact number for all cut-vertices, nor can it be determined just by the degree of the cut-vertex. I don't know of any generalized formula for how many components the deletion of a cut-vertex would add. I imagine the point of this question was for you to show that unlike cut-edges, cut-vertices do not add a predetermined number of components.

$\endgroup$
1
  • 1
    $\begingroup$ There is that limit though; the number of components after removal of a cut vertex is no more than the degree of the vertex. Which incidentally points up the impossibility of a cut vertex of degree 1. $\endgroup$
    – Joffan
    Mar 8, 2018 at 17:16

You must log in to answer this question.

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