K-edge-connected graph

Wikipedia: K-edge-connected graph

In graph theory, a graph is k-edge-connected if it remains connected whenever fewer than k edges are removed.

Formally, a graph $G$ with edge set $E (G)$ is k-edge-connected if $G \setminus X$ is connected for all $X \subseteq E(G)$ with $\left| X \right| < k$ .

Minimum vertex degree gives a trivial upper bound on edge-connectivity. If a graph $G$ is k-edge-connected then $k \le \delta(G)$ , where $δ(G)$ is the minimum degree of any vertex $v \in V(G)$ . This fact is clear since deleting all edges with an end at a vertex of minimum degree will disconnect that vertex from the graph.

	K-vertex-connected graph
	List of mathematics articles (K)
	SL (complexity)

	Program in c language using Depth first search DFS to convert each edge in Graph to a directed edge such that graph is strongly connected? Read answer...
	How do you connect two edges in blender? Read answer...
	How there will be negative edge weights in case of weighted graphs? Read answer...

	In depth first traversal of a graph G with n vertices k edges are marked as tree edges the no of connected components in G is?
	Draw a connected graph that becomes disconnected when any edge is removed from it?
	The minimum number of edges in a connected cyclic graph on n vertices is?

K-edge-connected graph

See also