Previous |  Up |  Next


connectivity; graph
In 1932 Whitney showed that a graph $G$ with order $n\geq 3$ is 2-connected if and only if any two vertices of $G$ are connected by at least two internally-disjoint paths. The above result and its proof have been used in some Graph Theory books, such as in Bondy and Murty's well-known Graph Theory with Applications. In this note we give a much simple proof of Whitney's Theorem.
[1] Bondy, J. A., Murty, U. S. R.: Graph Theory with Applications. Elsevier, New York (1976). MR 0411988
[2] Whitney, H.: Congruent graphs and the connectivity of graphs. Amer. J. Math. 54 (1932), 150-168. DOI 10.2307/2371086 | MR 1506881 | Zbl 0003.32804
[3] Whitney, H.: Non-separable and planar graphs. Trans. Amer. Math. Soc. 34 (1932), 339-362. DOI 10.1090/S0002-9947-1932-1501641-2 | MR 1501641 | Zbl 0004.13103
Partner of
EuDML logo