K-edge-connected graph

From Wikipedia, the free encyclopedia

In graph theory, a graph $G$ with edge set $E (G)$ is said to be $k$ -edge-connected if $G \setminus X$ is connected for all $X \subseteq E(G)$ with $\left| X \right| < k$ . In plain english, a graph is $k$ -edge-connected if the graph remains connected when you delete fewer than $k$ edges from the graph.

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.