every planar graph can be expressed as a union of five edge-disjoint forests

Question

How can I prove that every planar graph can be expressed as a union of (maximum) five edge-disjoint forests?

Only thing I can think about is going somehow like the $5$ color theorem but I get stuck in the middle. Or with induction, but still something doesn't fit. Can you help?

Answer 1

Use induction on the number of vertices. A planar graph $G$ has at most $3|V|-6$ edges, so there is at least one vertex $v$ of degree 5 or less.

Let $\{w_1,\ldots, w_j\}$; $j \le 5$ be $v$'s neighbors in $G$.

Then let $F_1,\ldots, F_5$ be the 5 edge-disjoint forests (some may be empty) such that $\cup_{j=1}^5 F_i = E(G \setminus \{v\})$. By induction such $F_1,\ldots, F_5$ exist.

Then for each $i \le j$ set $F'_i = F_i + \{v,w_i\}$, and (if $j$ is strictly less than 5) for each $i \in \{j+1,\ldots, 5\}$ set $F'_i=F_i$. Then each $F'_i$ is also a forest, and that each edge of $G$ is in one of the $F'_i$s. Make sure you can see why.

The above is about your answer (or at least enough for you to finish the proof).

Answer 2

More generally any graph $G$ can be expressed as a union of $\left\lceil\frac{|E(G)|}{|V(G)|-1}\right\rceil$ edge-disjoint forests since for every forrest $F\subseteq G$ with $V(F)=V(G)$ we have $|E(F\setminus G)|\leq |E(G)|-|V(G)|+1$. Thus if we let $F_{i+1}$ be any forrest spanning $G\setminus F_i$ with $F_0=\emptyset$ then the sequence terminates at an integer $n\leq \left\lceil\frac{|E(G)|}{|V(G)|-1}\right\rceil$ so we get $n$ edge disjoint forrests $F_1,\ldots F_n$ satisfying $G=\cup_{k=1}^nF_k$.

In your particular case note that if $G$ is planar then $\left\lceil\frac{|E(G)|}{|V(G)|-1}\right\rceil\leq 3$ thus every planar graph can be expressed as a union of $3$ edge-disjoint forests.