Prove that maximal outerplanar graphs are not bipartite

Question

I am trying to prove that a maximal outerplanar graph $G$ with $n \ge 3$ vertices cannot be bipartite. Intuitively, I think that all the inner faces will be triangles, thus forming odd length cycles, but I am not sure how to formalize that fact. Any ideas will be greatly appreciated!

Answer 1

You are on the right track, you are just missing the start of the argument that there need to be inner faces at all.

Assume you have a maximal outerplanar graph with $n\ge 3$ vertices. It obviously has to be connected to be maximal. It can't be a tree either, as a tree has actually no inner faces (no cycles) and thus you can just add any (not yet existing) edge and still have an outerplanar graph (this requires $n\ge 3$, as there simply aren't any edges you can add to the graph of 2 vertices and one edge).

Now that we know there must be a cycle in the graph, your arguments kicks in. The area enclosed by the cycle is the union of one or more inner faces. Take one of them. If it is a triangle, the graph can't be bipartite. If it is a $k$-gon with $k \ge 4$, you can take any diagonal of it and add it to the graph. It's still outerplanar, as you didn't add any vertices and didn't change the outer face at all.