2
$\begingroup$

I am new to graph theory and I am asked to prove this proposition in a homework assignment:

Prove that a cut-vertex in a simple undirected graph is not a cut-vertex of its complement graph.

A cut-vertex is defined as one vertex whose removal results in a disconnected graph. My question is: When we talk about a cut-vertex, do we assume the graph is connected in the first place? In other words, is the notion of a cut-vertex defined for disconnected graphs?

Take the proposition above for example. A graph and its complement may not be simultaneously connected. Let $G$ be a graph with three vertices $u,v,w$. Let us connect $uv$ and $vw$. Then its complement has $u,v,w$ as vertices and only one edge $uw$, and is not connected. And in this case it may not make sense to say "prove something is not a cut-vertex" when you don't know the graph is connected or not.

Can someone clarify this for me? Thanks in advance!

$\endgroup$
0

2 Answers 2

4
$\begingroup$

In general, definitions are not set in stone. When we define "cut vertex", we are thinking of connected graphs, and usually don't have to make a decision about what to do with disconnected ones. If you run into an application where it matters, you should make a decision that generalizes the usual one. I think there are two things that obviously make sense as generalizations:

  • $v$ is a cut vertex of $G$ if $G-v$ is disconnected (whether that's because $G$ was already disconnected, or because deleting $v$ disconnected it).
  • $v$ is a cut vertex of $G$ if it is a cut vertex of one of the connected components of $G$ (that is, if $G-v$ has more connected components than $G$).

But there could be other cases I'm not thinking of. Anyway, as long as you say what you mean, you can pick any option you like.

In this specific problem, there's only one unusual edge case. For an example of it, let $G$ consist of two $n$-cliques and a single vertex $v$ adjacent to every vertex in both cliques. (Then $v$ is a cut vertex of $G$.) In the complement, we have a complete bipartite graph $K_{n,n}$ and an isolated vertex $v$. For the problem to be valid, we don't want to consider $v$ to be a cut vertex in such a case, and I can't think of how you would.

$\endgroup$
1
  • $\begingroup$ Thanks. This explanation indeed makes more sense than what I had in mind, and is consistent with the proposition that I am trying to prove. $\endgroup$
    – trisct
    Mar 15, 2020 at 15:16
2
$\begingroup$

A graph and its complement can both be connected.

Take for example $4$ vertices, the vertex set $V : \{ a, b, c, d\}$ and the edge set $ E: \{ ac, bc, bd\}$. Both the graph and its complement are connected.

Also, $c$ is a cut vertex in this graph but not in its complement.

A cut vertex is any vertex whose removal increases the number of connected components.. So yes, $G$ could be disconnected, but we can talk about its cut vertex

$\endgroup$
3
  • $\begingroup$ Do you mean that if we say $v$ is (or is not) a cut-vertex of $G$, we take by default that $G$ is connected? $\endgroup$
    – trisct
    Mar 15, 2020 at 14:59
  • $\begingroup$ @trisct I think $G$ may be disconnected but the number of connected components of G must increase after removing all the edges containing that cut vertex $\endgroup$
    – ab123
    Mar 15, 2020 at 15:02
  • $\begingroup$ @trisct I think the definition I linked to might help $\endgroup$
    – ab123
    Mar 15, 2020 at 15:06

You must log in to answer this question.

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