Graphs with \(3n-6\) edges not containing a subdivision of \(K_5\) (Q2568497)

Let \(G_1, G_2,\ldots,G_m\), \(m \geq 1\), be a sequence of maximal planar graphs and suppose \(D_i\) is a triangle in \(G_i\). Let \(G_{1,2}\) be obtained from \(G_1\) and \(G_2\) by identifying \(D_1\) and \(D_2\). Now take a triangle \(D_{1,2}\) in \(G_{1,2}\) and identify it with the triangle \(D_3\) in \(G_3\) and let \(G_{1,2,3}\) be the resulting graph. Continue in this manner until \(G=G_{1,2,\ldots,m}\) has been constructed. Then \(G\) has \(3|G|-6\) edges and does not contain a subdivision of \(K_5\). Let \(\mathcal{A}\) be the collection of graphs that can be constructed in this manner. It is shown in this paper that if \(H\) is a graph with \(n\) vertices and \(3n-6\) edges that does not contain a subdivision of \(K_5\), then \(H \in \mathcal{A}\). It is observed that this result together with a proof due to \textit{A. E. Kézdy{ and \textit{P. J. McGuinness} [J. Graph Theory 15, No.~4, 389--406 (1991; Zbl 0747.05037)] yield a proof of a conjecture made by Thomassen, namely, that every non-planar, 4-connected graph \(G\) with at least \(3|G|-6\) edges contains a subdivision of \(K_5\).}}