Number of simple edge-disjoint paths needed to cover a planar graph

Question

Let $G=(V,E)$ be a graph with $|E|=m$ of a graph class $\mathcal{G}$. A path-cover $\mathcal{P}=\{P_1,\ldots,P_k\}$ is a partition of $E$ into edge-disjoint simple paths. The size of the cover is $\sigma(\mathcal{P})=k$. I am interested in upper and lower bounds for the quantity

$$ \max_{G\in \mathcal{G}} \quad \min_{\mathcal{P} \text{ is path-cover of $G$}} \sigma(\mathcal{P})/m.$$

In other words, how large is the inverse of the average path length in the smallest path-cover in the worst case.

The graphs classes $\mathcal{G}$ I am interested in are (1) planar 3-connected graphs, and (2) triangulations.

There is a simple observation for a lower bound: In every odd-degree vertex one path has to start/end. So when all vertices have odd degree there any path-cover needs at least $m/6+1$ paths (a triangulation has $3|V|-6$ edges). You get the same result by noticing, that $(n-1)/2$ paths have to pass through a vertex of degree $n-1$.

Is a path-cover with $\frac{m}{6}$ paths always possible for planar graphs?

I am aware of a few results covering planar graphs with paths of length $3$.

Here is an example of a path-cover of the graph of the icosahedron.

Answer 1

I will show that $\frac{m}{6}$ is not enough for 3-connected planar graphs. The following is inspired by fedja's comment (and also some nice discussion with Krystal Guo).

Consider the prism graph, which we will denote $P_n$. We say it has $2n$ vertices and $3n$ edges. Then in this case $\frac{m}{6} = \frac{n}{2}$. We will show that $\sigma(P_n) =n $. It is clear that $n$ paths is enough.

Consider the following graphs which we denote $T_n$:

and so on.. Note that $T_n$ has $3n - 1$ edges and $2n+2$ vertices.

It is not too hard to show that $\sigma(T_n) = n+1$ (and this is the best possible). One can show by induction, considering the left most edge between the upper and lower paths.

Let $p_1 , \ldots , p_k$ be a path cover of $P_n$. Now $P_n$ is two copies of $C_n$ with a matching, $M$, in between them. If every $e \in M$ is actually some $p_i$, then we have $k \geq n+2$.

So we may assume there is a $e = (u,v)$ such that the path, $p_i$, that contains $e$, contains at least one more edge, wolog say $(v,w)$.

$(i)$ The vertex $u$ is also contained in another edge of $p_i$ (other than $e$). Then $(V(P_n) , E(P_n) \setminus E(p_i))$ is $T_n$ minus at most two paths (actually, exactly two: the two paths start with precisely the two edges incident to $e$, respectively). In this case $k \geq n+1 - 2 + 1 = n$ (the last $+1$: don't forget to count $p_i$).

$(ii)$ The vertex $u$ is not contained in any other edge of $p_i$. Then let $p_j$ be another path that contains $u$. Then $(V(P_n) , E(P_n) \setminus (E(p_i)\cup E(p_j))$ is a $T_n$ minus at most 3 paths ($p_i$ is one path in $T_n$ and $p_j$ is at most two paths in $T_n$). It follows that $k \geq n + 1 - 3 +2= n$.

Thus we obtain $\sigma(P_n) = n$, as desired.