Edge Connectivity

• A Disconnecting set in a connected graph is a set of edges whose removal disconnects .
  • In general, a disconnecting set increases the number of components.
• A cut-set is a disconnecting set such that no proper subset of it is a disconnecting set.
  • (Wilson e5.11b) If two distinct cut-sets of contain an edge , then has a cut-set that does not contain ¹

• A bridge is a cut-set with only one edge.

  • (Theorem): If is a bridge, then it appears in every spanning forest.
    • If it didn’t then the spanning forest would not be able to cover all vertices since removing it disconnects the graph.

• Let be a connected graph. The edge connectivity of , denoted is the size of the smallest cut-set in .

  It is the minimum number of edges we need to delete to disconnect .

  If , we say that is -edge connected

• (Wilson 28.1) Menger’s Theorem (Edge Version) - the maximum number of edge-independent paths connecting two distinct vertices and of a connected graph is equal to the minimum number of edges in a -edge cut.

• An edge atom of a graph is defined as such that

  • (Godsil 3.3.2) Any two distinct edge atoms are vertex disjoint

    • Proof: Let be two distinct edge atoms of . If , then since neither nor contain more than half the vertices of , we have

      Hence .

      Consider the other case, . By (Godsil 3.3.1)

      But also

      But this is impossible since which contradicts the fact that so

Links §

• Introduction To Graph Theory by Wilson

• Algebraic Graph Theory by Godsil and Royle

• Fundamental Constructs of Graph Theory

• Operations on Graphs

• Vertex Connectivity

Footnotes §

1. Each cut set partitions the graph into and respectively. Clearly and cannot be empty (show this is true). The cut-set and whichever is non-empty is the one we desire. Demonstrate cannot be in this cut-set either ↩