What is vertex connectivity of triangle graph?

Question

On Wikipedia, it says that the vertex connectivity of a triangle graph is 2.

In my opinion, if we removed any 2 vertices in a triangle graph, then the remaining vertex would be a trivially connected graph. And even if we remove all 3 vertices, then the empty graph is also trivially connected. Perhaps a triangle graph doesn't have a vertex connectivity?

So what is the vertex connectivity of a triangle graph?

Answer 1

The usual definition of vertex connectivity (a graph is $k$-vertex-connected if we cannot disconnect it by removing fewer than $k$ vertices) doesn't really work for the triangle graph or for any other complete graph.

(You could argue that the empty graph is not connected, in which case the triangle graph could have vertex connectivity $3$.)

However, for all other graphs, an alternate characterization of vertex connectivity exists: a graph is $k$-vertex-connected if, for any two vertices $v$ and $w$, there exist $k$ paths from $v$ to $w$ which disjoint except at their endpoints. (The equivalence between these is Menger's theorem.) So we can take this definition instead, and get the same notion for non-complete graphs.

Under this definition, the triangle graph is $2$-vertex-connected, because there are two disjoint paths between any two of its vertices, and in general the complete graph $K_n$ is $(n-1)$-vertex-connected.

---

In fact, to match this result, we often add a clause into the usual definition to make it work for complete graphs in the same way. For example, Wikipedia's definition of a $k$-vertex-connected graph is

a connected graph $G$ is said to be $k$-vertex-connected (or $k$-connected) if it has more than $k$ vertices and remains connected whenever fewer than $k$ vertices are removed.

The condition "it has more than $k$ vertices" only comes into play for a complete graph $K_n$, and ensures that its vertex connectivity is $n-1$.