If graph and then is the induced subgraph with edges in deleted. Given then is the spanning subgraph obtained by deleting edges in .
A graph is connected if and is connected for any with .
The only connected graph with vertices is the complete graph .
The connectivity of or isconnected.
If distinct and the local connectivity has no path , the minimum number vertices separating and .
If is not complete then , which is the same as .
If is complete then does not have a value, but .
A graph is -edge connected if is connected for all with .
The edge connectivity of is is edge connected.
Vertex form. Let distinct. then maximum number of pairwise independent paths.
Edge form. distinct. Then maximum number of edge disjoint paths.
Edge form. Do the same thing but use the edge form of max-flow min-cut.
The line graph is the graph with a vertex for each and an edge whenever and have a common end vertex in .
Assume and let . Then .
All cases imply that .
A graph is -connected iff any two vertices are joined by at least independent paths.
is -connected iff , so true for a complete graph.
A graph is -edge-connected iff any two vertices are joined by at least edge disjoint paths.
John Fremlin 2010-02-17