While working through some problems concerning planarity, I encountered one asking me to prove that every graph with at most three cycles is planar. Being rather elementary in my knowledge of Graph Theory, I have tried approaching this through use of Kuratowski's Theorem:
A finite graph is planar if and only if it does not contain a sub-graph that is homeomorphic to $K_5$ or $K_{3,3}$.
However, from what I have observed $K_{3,3}$ has 10 cycles. In this way, recognizing that neither isolating a sub-graph nor subdividing said sub-graph can create new cycles, it would appear that a graph would need at least 10 cycles to be non-planar. I have been unable to identify any graph with fewer than ten cycles which proves non-planar. Any help as to what I am missing here would be greatly appreciated. Thanks!
I think this would work :
Let G be a graph with at most three cycles.
Without loss of generality we consider G to be a simple 2-connected graph.
(Why simple? - because if G is non-planar, removal of loops and multiple edges of G must result in a subgraph of G which is also non-planar.
Why 2-connected? - A graph is planar if and only if each of it's blocks is planar. Hence, while testing the planarity of a graph G, one may assume G to be a block and hence 2-connected.)
Now, let G has only one cycle say C1 of length k, then all the vertices of G must be in C1 (otherwise since G cannot have any more cycles, G\C1 contains a tree connected to C1 by a cut-vertex of G - a contradiction to - G is 2-connected). Hence G itself is a cycle and hence is planar.
Let G has another cycle C2, then for a vertex u in C1 which is not in C2 and another vertex v in C2 which is not in C1, u & v must lie on a common cycle, say C3. (Since G is 2-connected). Now, G cannot have any more cycles and G is 2-connected implies C1 is adjacent to C2 (have a common set of adjacent edges) so that the cycle C3 can be formed.
Again, all the vertices of G must be in C1 or C2 (otherwise since G cannot have any more cycles, G \ C1UC2 contains a tree connected to C1 or C2 by a cut-vertex of G - a contradiction to - G is 2-connected). Therefore, G is a cycle adjoined to another cycle and hence is a planar graph having three faces.
Thank you!