7
$\begingroup$

Given a graph $G$ with $7$ vertices, either $G$ or its complement must be planar.

The closest thing to this question that I've found on the internet is this but since it uses Euler's formula, I can't use it to prove planarity. I've tried to approach it using Kuratowski's and Wagner's Theorem but I can't figure out how. The sum of the edges of $G$ and its complement should be equal to $21$ which doesn't help me because two $K_5$ subgraphs have only $20$ edges.

$\endgroup$
4
$\begingroup$

Suppose $G$ is a nonplanar graph of order $7.$ By Kuratowski's theorem, $G$ has a subgraph $H$ which is either a subdivision of $K_5$ or a subdivision of $K_{3,3}.$ A subdivision of $K_5$ has $5$ vertices of degree $4$; a subdivision of $K_{3,3}$ has $6$ vertices of degree $3.$ If $H$ is a subdivision of $K_5,$ then $\bar G$ has at least $5$ vertices of degree $\le2,$ and therefore (by Kuratowski's theorem) must be planar. Therefore, we may assume that $H$ is a subdivision of $K_{3,3}.$ Since $G$ has only $7$ vertices, either $H=K_{3,3},$ or else $H$ is obtained from $K_{3,3}$ by replacing one edge of $K_{3,3}$ with a path of length $2.$ In either case it is easy to check that the graph $K_7-E(H)$ (and therefore its subgraph $\bar G$) is planar.

On the other hand, the graph $G=K_{3,3}+2K_1$ is a nonplanar graph of order $8$ whose independence number is $5$; thus both $G$ and $\bar G$ are nonplanar graphs.

| cite | improve this answer | |
$\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.