Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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.
