A remark on the connectivity of the complement of a 3-connected graph (Q1916372): Difference between revisions

A finite simple graph \(\Gamma\) is said to be bi-3-connected if both \(\Gamma\) and its complement \(\overline\Gamma\) are 3-connected. A 2-set of vertices whose contraction results in a bi-3-connected graphe is called a bi-contractible pair. The one main result of this paper is that every bi-3-connected graph on at least 22 vertices admits a bi-contractible pair. This result is analogous to one by \textit{W. T. Tutte} [Nederl. Akad. Wet., Proc., Ser. A 64, 441-455 (1961; Zbl 0101.40903)] that every 3-connected graph on at least five vertices admits an edge whose contraction leaves a 3-connected graph. The authors believe their lower bound on the number of vertices to be inessential and conjecture that every bi-3-connected graph admits a bi-contractible pair.