k-Connected Graph
A graph 
on more than two vertices is said to
be 
-connected (or 
-vertex connected,
or 
-point connected) if there does not exist
a vertex cut of size 
whose removal
disconnects the graph, i.e., if the vertex connectivity 
. Therefore, a connected
graph on more than one vertex is 1-connected and a biconnected
graph on more than two vertices is 2-connected.
The singleton graph is "annoyingly inconsistent" (West 2000, p. 150) since it is connected (specifically, 1-connected), but by
convention it is taken to have 
.
The path graph 
is also problematic,
since for the purpose of theorems such as those involving unit-distance graphs it
is convenient to regard it as biconnected, yet it has vertex connectivity of 
.
The wheel graph is the "basic 3-connected graph" (Tutte 1961; Skiena 1990, p. 179).
-connectedness graph checking is implemented
in the Wolfram Language as KVertexConnectedGraphQ[g,
k].
The following table gives the numbers of 
-connected graphs
for 
-node graphs (counting the singleton
graph 
as 1-connected and the path
graph 
as 2-connected).
 | OEIS |  -connected graphs on 1, 2, ... nodes |
| 1 | A001349 | 1, 1, 2, 6, 21, 112, 853, 11117, 261080, ... |
| 2 | A002218 | 0, 1, 1, 3, 10, 56, 468, 7123, 194066, ... |
| 3 | A006290 | 0, 0, 0, 1, 3, 17, 136, 2388, 80890, ... |
| 4 | A086216 | 0, 0, 0, 0, 1, 4, 25, 384, 14480, ... |
| 5 | A086217 | 0, 0, 0, 0, 0, 1, 4, 39, 1051, 102630, 22331311, ... |
| 6 | A324240 | 0, 0, 0, 0, 0, 0, 1, 5, 59, 3211, 830896, ... |
| 7 | A324092 | 0, 0, 0, 0, 0, 0, 0, 1, 5, 87, 9940, 7532629, ... |
Contact the MathWorld Team
graph properties