0
$\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$
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
    $\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 '18 at 17:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.