$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\u2a7d\kappa (G)\in \mathrm{\U0001d5a8\U0001d5ad}$. 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$edgeconnected for any $k\u2a7d{\kappa}^{\prime}(G)\in \mathrm{\U0001d5a8\U0001d5ad}$. And note “removing an edge” is simply that; it does not entail removing any vertices.

•
If ${\kappa}^{\prime}(G)=0$ also $\kappa (G)=0$ and vice versa; such graphs are called disconnected and consist of several connected components^{}. If $\kappa $ and ${\kappa}^{\prime}$ are nonzero (the graph is 1connected) it is a connected graph (a single connected component)

•
If ${\kappa}^{\prime}(G)=1$ the graph contains at least one bridge. If ${\kappa}^{\prime}(G)>1$ (the graph is 2edgeconnected) every edge is part of a cycle (circuit^{}, closed path).
If $\kappa (G)=1$ the graph contains at least one cutvertex. If $\kappa (G)>1$ (the graph is 2vertexconnected) there is, for any pair of vertices, a cycle they both lie on.

•
For the complete graphs^{} we have $\kappa ({K}_{n})={\kappa}^{\prime}({K}_{n})=n1$.

•
For any graph $G$ we have $\kappa (G)\u2a7d{\kappa}^{\prime}(G)\u2a7d\delta (G)$ where the latter is the minimum valency^{} in $G$ (the valency of a vertex is the number of edges sprouting from it).
Everything on this page applies equally well to multigraphs^{} and pseudographs^{}.
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 

Canonical name  kconnectedGraph 
Date of creation  20130322 13:10:58 
Last modified on  20130322 13:10:58 
Owner  marijke (8873) 
Last modified by  marijke (8873) 
Numerical id  7 
Author  marijke (8873) 
Entry type  Definition 
Classification  msc 05C40 
Related topic  ConnectedGraph 
Related topic  ClosedPath 
Defines  $k$connected $k$vertexconnected $k$edgeconnected connectivity 