1
$\begingroup$

I know that a graph is planar if and only if it contains no subgraph homeomorphic to $K_5$ or $K_{3,3}$, and I know that the Triakis Tetrahedral Graph is planar (http://mathworld.wolfram.com/TriakisTetrahedralGraph.html).

An additional edge added to the Triakis Tetrahedral will result in a non-planar graph (visually this is apparent). But what is the foundation of this? Is there now a $K_{3,3}$ subgraph? Is there an easy way to show which graphs can be superimposed to form this new graph (with the additional edge)?

$\endgroup$
2
$\begingroup$

The easiest way to prove this is not to worry about $K_5$ or $K_{3,3}$, but instead use the fact that a planar graph on $n$ vertices has at most $3n-6$ edges (as proven, e.g., here). Since the triakis tetrahedral graph has $8$ vertices and $18=3(8)-6$ edges, adding any edge to it will give you a graph with too many edges to be planar.

Kuratowski's theorem will then tell you that the resulting graph has a subgraph homeomorphic to either $K_5$ or $K_{3,3}$, but I don't know of an easy way to find it. If you really want this subgraph and not just a proof of non planarity, you might have to consider each possible way of adding an edge separately.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.