Skein (graph theory)

A skein in a graph ⁠${\displaystyle G}$⁠ is a subgraph of ⁠${\displaystyle G}$⁠ that is the union of a collection of paths between two distinct vertices that have only these two vertices in common.

Let ⁠${\displaystyle G}$⁠ be a graph, and ⁠${\displaystyle a}$⁠ and ⁠${\displaystyle b}$⁠ be two distinct vertices of ⁠${\displaystyle G}$⁠. An ⁠${\displaystyle (a,b)}$⁠-skein of strength ⁠${\displaystyle k}$⁠, where ⁠${\displaystyle k}$⁠ is a cardinal number, is then the union of a set of ⁠${\displaystyle k}$⁠ paths joining ⁠${\displaystyle a}$⁠ and ⁠${\displaystyle b}$⁠ such that any two of these paths have only ⁠${\displaystyle a}$⁠ and ⁠${\displaystyle b}$⁠ in common. The skein is then also called a ⁠${\displaystyle k}$⁠-skein.

For a ⁠${\displaystyle k}$⁠-skein in a finite graph, ⁠${\displaystyle k}$⁠ is a natural number.

The graph displayed in the image contains a 4-skein. The four paths that form the skein connect the pair of vertices and the edges of these paths are indicated by showing them in red. As the graph has no pair of vertices whose degrees are larger than four, it does not contain a 5-skein.

Using the notion of a skein, Menger's theorem can be formulated as follows:

The size of any minimum cut of a given finite graph is equal to the maximal value of ⁠${\displaystyle k}$⁠ for which the graph contains a ⁠${\displaystyle k}$⁠-skein.

• Halin, R. (1997). "Minimization Problems for Infinite n-Connected Graphs". In Bollobás, Béla; Thomason, Andrew (eds.). Combinatorics, Geometry and Probability. Cambridge University Press. p. 356. ISBN 0--521--58472-8.
• Hemminger, Robert L.; Beineke, Lowell W. (1978). "10. Line Graphs and Line Digraphs". In Beineke, Lowell W.; Wilson, Robin J. (eds.). Selected Topics in Graph Theory. Academic Press. p. 277. ISBN 0-12-086250-6.