Planar graph with 9 vertices and 3 components property

Question

I have been preparing for graph theory exams and found a statement that:

Let $G$ be a planar graph with 9 vertices and 3 components. Then complement of graph $G$ is not a planar graph.

How can we try to prove it using theorems from graph theory?

Answer 1

In the first place, if two of the components of $G$ each have at least $3$ vertices, then the complement $G'$ contains a $K_{3,3}$ and is nonplanar. Furthermore as pointed out by Misha Lavrov, if there is a component with between $3$ and $6$ vertices, then we can pick $3$ vertices in the component and $3$ in the complement to get a $K_{3,3}$

The only remaining case is when two of the components are isolated vertices and the remaining component, $C$ has order $7$. Let the isolated vertices be $a$ and $b$ and suppose $C$ has a vertex $c$ of degree less than $4$. Then there are distinct vertices $x,y,z\neq c$ in $C$ to which $c$ is not adjacent to. Then in $G'$ each of $a,b,c$ is adjacent to each of $x,y,z$ so $G'$ is nonplanar.

We may therefore assume that every vertex of $C$ has degree at least $4$. Since $C$ is planar, it has at most $3(7-2)=15$ edges, so $C'$ has at least $21-15=6$ edges. In $G'$, each of the isolated vertices is adjacent to every vertex in $C$, and the two isolated vertices are adjacent to each other, giving at least $6+7+7+1=21$ edges in $G'$. But a planar graph on $9$ vertices has at most $3(9-2)=21$ edges, so in fact $C$ has $15$ edges, and the sum of its vertex degrees is $30.$ That leaves only two possible degree sequences for $C$: $6,4,4,4,4,4,4$ or $5,5,4,4,4,4,4.$

I have arguments disposing of both of these cases, or at least I think I do, but they are long and consist of showing that a planar graph with either degree sequence cannot exist, by trying to construct one, and verifying that the attempt must fail. It doesn't seem worthwhile to type them here. I started typing the case where one vertex has degree $6$, but quit in the middle because I didn't think anyone would read it.

It seems to me that once we know the minimum degree of $C$ is $4$, there ought to be a way of showing it has a $K_5$ minor, but I can't see how to do it.

Answer 2

With $3$ components and $9$ vertices, there must be a component $C$ with at least $3$ vertices. If $C$ contains between $3$ and $6$ vertices, there is a $K_{3,3}$ formed in $G'$ (the complement of $G$) by taking three vertices in $C$ and three outside $C$. Also, $C$ cannot contain more than $7$ vertices, because there are two other components with at least one vertex each.

So it remains to consider the case when $C$ has order $7$, and $G$ has two vertices $x,y$ not in $C$. In $G'$, $x$ and $y$ are adjacent to every vertex of $C$.

If $G'[C]$ (the subgraph of $G'$ induced by $C$) contains a cycle, then $G'$ contains a subdivision of $K_5$ whose key vertices are $x$, $y$, and three vertices on the cycle. So $G'$ is not planar.

If $G'[C]$ contains a vertex $z$ of degree $3$ or more, then $G'$ contains a $K_{3,3}$: put $x,y,z$ on one side, and the neighbors of $z$ on the other side. So $G'$ is not planar.

Otherwise, $G'[C]$ is a forest in which all vertices have degree at most $2$: a forest in which all trees are paths. As a result, it is a subgraph of the path on $7$ vertices $v_1, v_2, \dots, v_6, v_7$ connected in that order. But now each of $v_1, v_2, v_3$ is connected to each of $v_5, v_6, v_7$ in $G$, forming a $K_{3,3}$ in $G$. So $G$ is not planar, contrary to assumption!

Therefore $G$ and $G'$ cannot both be planar.