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!
Best Answer
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:
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.