Non-contractible edges in a 3-connected graph (Q1900184): Difference between revisions

Given a simple finite graph \(G\) and an edge \(e\) of \(G\), denote by \(Ge\) the graph obtained by identifying the two vertices incident with \(e\) and deleting any resulting loops and multiple edges. If \(G\) is 3-connected but \(Ge\) is not 3-connected, then \(e\) is said to be non-contractable. It is shown that if \(G\) is a 3-connected graph on \(p > 4\) vertices then the number of non-contractible edges of \(G\) is at most \(3p - \lfloor 3 (\sqrt {24p + 25} - 5)/2 \rfloor\). While this result is best possible in the sense that there exist arbitrarily large graphs that attain this bound, it is claimed (proof omitted because of its length) that the slightly sharper upper bound of \(\lfloor 3 [p - (\sqrt {24p + 25} - 5)/2] \rfloor\) is also valid.