Let $G$ be a connected planar graph with a planar embedding where every face boundary is a cycle of even length. Prove that $G$ is bipartite.
Any hints/tips will be greatly appreciated.
[Math] Proving bipartition in a connected planar graph
graph theory
Related Solutions
Is this enough of a proof? I would have to say no.
If every face boundary is a cycle of even length, every face has an even degree. This is essentially saying "If X, then X." The catch is that there might be cycles that are not face boundaries.
There are no cycles of odd degree and the graph must be bipartite. This is what we need to prove (and we need to do more than assert that it is true).
May I suggest this approach:
Assume the graph has an odd cycle $C$. Assume $C$ is a minimum length cycle.
If $C$ is not a face boundary, then [???], so we can find an odd-length cycle smaller than $C$, giving a contradiction. So $C$ is a face boundary.
However, this contradicts the initial hypothesis: every face boundary is a cycle of even length.
Checking if a given graph has a Hamiltonian path is hard; however, cooking up examples of graphs that definitely don't have Hamiltonian paths is much easier. For example, if the graph didn't have to be planar, then you could take the complete bipartite graph $K_{6,8}$. This does not have a Hamiltonian path because any path alternates sides of the graph, but this bipartite graph is unbalanced so you would run out of vertices on the side with $6$ vertices before visiting all of the vertices on the other side.
There is a planar example that fails to have a Hamiltonian path for a similar reason: the skeleton graph of the rhombic dodecahedron. This polyhedron is constructed by putting square pyramids on the faces of a cube in such a way that the sides of adjacent pyramids line up and we end up with six diamond-shaped faces.
The graph is a subgraph of $K_{6,8}$: the vertices that were vertices of the cube are only adjacent to the vertices that form the tips of the pyramids, and vice versa. So it's bipartite and not Hamiltonian. It's planar and $3$-connected because it's the skeleton graph of a polyhedron: the polyhedral graphs are precisely the $3$-connected planar graphs.
Finally, here is one way to solve this problem that probably goes against the spirit of the exercise but is very much in the spirit of doing independent work in graph theory. Go to the House of Graphs and run the following search:
- Require a specific (numeric) value for an invariant: "Number of vertices equal to 14" and "Vertex Connectivity greater than or equal to 3"
- Only consider certain classes of graphs: "Planar", "Bipartite", and NOT "Traceable".
This will give you exactly one result, which is the rhombic dodecahedral graph.
Best Answer
Hint:
I hope this helps ;-)