In the Wiki:
https://en.wikipedia.org/wiki/Connectivity_(graph_theory)
It says:
A complete graph with n vertices, denoted $K_n$, has no vertex cuts at all.
Also, the node connectivity of a complete graph ($n$ nodes) is $n-1$
I review the definition of "vertex cut" or "cut" in wiki:
https://en.wikipedia.org/wiki/Cut_(graph_theory)
a cut is a partition of the vertices of a graph into two disjoint subsets. Any cut determines a cut-set, the set of edges that have one endpoint in each subset of the partition.
I really have no idea why a complete graph has no vertex cut by the definition? (I can still do the following:
Best Answer
I am answering this because I don't have the reputation to comment yet. I was reading through the Wiki article you linked to on Connectivity. The problem is that the term "vertex cut" is defined differently on that article. It is defined as : "A cut, vertex cut, or separating set of a connected graph G is a set of vertices whose removal renders G disconnected." This is indeed the definition of a vertex cut. (https://proofwiki.org/wiki/Definition:Vertex_Cut) If you use this definition, then indeed it is true that $K_n$ has no vertex cut. We can simply remove any set of vertices we want to and then prove that each vertex is still connected to each other vertex and hence the graph is still connected. I think it is just a problem with the definitions that you are facing.