Note on Whitney’s Theorem for \(k\)-connected

Guantao Chen1, Ralph J.Faudree2, Warren E.Shreve3
1Department of Mathematics North Dakota State University Fargo, ND 58105
2Department of Mathematical Sciences Memphis State University Memphis, TN 38152
3 Department of Mathematics North Dakota State University Fargo, ND 58105

Abstract

In this paper we refine Whitney’s Theorem on \(k\)-connected graphs for \(k \geq 3\). In particular we show the following: Let \(G\) be a \(k\)-connected graph with \(k \geq 3\). For any two distinct vertices \(u\) and \(v\) of \(G\) there are \(k\) internally vertex disjoint paths \(P_1[u,v], P_2[u,v], \dots, P_k[u,v]\) such that \(G – V(P_i(u,v))\) is connected for \(i = 1, 2, \dots, k\), where \(P_i(u, v)\) denotes the internal vertices of the path \(P_i[u, v]\). Further one of the following properties holds:

  1. \(G – V(P_i[u, v])\) is connected for \(i = 1, 2, 3\).
  2. \(G – V(P_i[u, v])\) is connected for \(i = 1, 2\) and \(G – V(P_i[u, v])\) has exactly two connected components for \(i = 3, 4, \dots, k\).

In addition, some other properties will be proved.