# ${k}$-connected graph

Connectivity of graphs, when it isn’t specified which flavor is intended, usually refers to vertex connectivity, unless it is clear from the context that it refers to edge connectivity.

The (vertex) connectivity $\kappa(G)$ is the minimum number of vertices (aka nodes) you have to remove to either make the graph no longer connected   , or reduce it to a single vertex (node). $G$ is said to be $k$-(vertex)-connected for any $k\leqslant\kappa(G)\in{\mathchoice{{\sf I\kern-1.2ptN}}{{\sf I\kern-1.2ptN}}{{% \scriptstyle\sf I\kern-1.2ptN}}{{\scriptscriptstyle\sf I\kern-1.2ptN}}}$. Note that “removing a vertex” in graph theory  also involves removing all the edges incident   to that vertex.

The edge connectivity $\kappa^{\prime}(G)$ of a graph $G$ is more straightforward, it is just the minimum number of edges you have to remove to make the graph no longer connected. $G$ is said to be $k$-edge-connected for any $k\leqslant\kappa^{\prime}(G)\in{\mathchoice{{\sf I\kern-1.2ptN}}{{\sf I\kern-1% .2ptN}}{{\scriptstyle\sf I\kern-1.2ptN}}{{\scriptscriptstyle\sf I\kern-1.2ptN}}}$. And note “removing an edge” is simply that; it does not entail removing any vertices.

For directed graphs  there are two notions of connectivity (http://planetmath.org/ConnectedGraph) (“weak” if the underlying graph is connected, “strong” if you can get from everywhere to everywhere).

There are now pictures (http://planetmath.org/ExamplesOfKConnectedGraphs) to go with this entry.

Title ${k}$-connected graph kconnectedGraph 2013-03-22 13:10:58 2013-03-22 13:10:58 marijke (8873) marijke (8873) 7 marijke (8873) Definition msc 05C40 ConnectedGraph ClosedPath ${k}$-connected ${k}$-vertex-connected ${k}$-edge-connected connectivity