I'm reading this paper (Every Planar Graph with Nine Points Has a Nonplanar Complement). As part of Proposition 1, it states that if graph $G$ has
- at least 7 vertices
- and its complement $\overline{G}$ contains 2 components
- with each component of $\overline{G}$ containing at least 3 vertices
then $G$ contains $K_{3,3}$ as a subgraph.
This confused me, though. Isn't this true not just for graphs with at least 7 vertices, but also for graphs with 6 vertices? After all, if you have 3 vertices each in 2 non-connected components in the complement, wouldn't that mean that they contain a complete bipartite graph as a subgraph, and wouldn't this be $K_{3,3}$?
Apologies if this is basic, but I'm feeling confused. Any help?
Yes, that seems true, by your argument. Maybe the author of the paper considered that so trivial as to not be worthy further mentioning.