Prove there is a path of length 6

Question

Prove that if $G$ is a planar bipartite graph and each vertex has degree at least 3, then $G$ contains a path of length $6$.

Since the graph is planar and bipartite

$\sum_{v \in G} deg(v) = 2e$ where $e$ is # of edges.

Now suppose $P = v_0v_1v_2v_3v_4v_5$ is the longest path and has length 5 (for sake of contradiction).

However since $v_5$ has degree at least $3$ it must have 2 more neighbors in $P$

But at this point I am getting stuck. Any tips?

Answer 1

Try drawing a bipartite planar graph in which every vertex has degree at least three. In a bipartite graph, the vertices can be colored with two colors, red and blue. So the graph has to have at least one red vertex, $a_1$, with three blue neighbors, $b_1, b_2, b_3$. Now $b_1$ needs two extra red neighbors, $a_2$ and $a_3$... If you try to continue this construction, you'll find that if you're not careful, you end up drawing $K_{3,3}$. If you avoid that, then you'll end up with a path of length $5$.

So now you've proven that a graph satisfying your conditions must have a path of length $5$. Now zoom in on that path, say $v_1v_2v_3v_4v_5$. All you need to do is prove that $v_5$ (or $v_6$) has an extra neighbor somewhere. You can do this using only bipartness and the degree condition, you don't need planarity anymore.

Answer 2

(We need to assume there is a vertex; it's false for the empty graph.)

Since there are no degree-$1$ vertices, the graph contains a cycle $C_k$. Moreover, the cycle has length in $\{4,6,8,\ldots\}$, since the graph is bipartite. If $k \geq 8$, then this cycle contains a $6$-edge path.

If $k=6$, then since this $C_6$ does not induce a complete bipartite $K_{3,3}$ subgraph (since the graph is planar), some vertex in it is adjacent to a vertex outside the $C_6$:

This subgraph contains a $6$-edge path.

If $k=4$, then we consider neighbors of the $4$-cycle belonging to a subgraph depicted below:

If $x$ and $y$ are adjacent, then we have a $C_6$ subgraph, which is the $k=6$ case.

If $x$ and $y$ are not adjacent, then $x$ is adjacent to a non-depicted vertex (since it has degree $\geq 3$), which gives a $6$-edge path.