graph theory
Given a simple undirected connected graph. What is the minimum number of edge-disjoint paths needed to cover all edges of the graph? I have only found information about the vertex-covering one.
My friend suggests that such value equals u/2, with u being number of vertices with odd degree, or 1 if there is no such vertices.
Can anyone confirm if his assumption is correct or not?
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.
It is not necessarily that each path $P_i$ contains exactly one of $\{v_1, \cdots, v_k\}$. A counterexample is as follows.
Counterexample. The following figure shows a $2$-edge-connected graph, where $v$ is green, $v_1$ is blue and $v_2$ is red. As you can see, every path from $v$ to $v_2$ must pass $v_2$.
However, it is true that $P_i$ and $P_j$ are edge-disjoint if $i \neq j$. To prove this, you can construct a new graph $G'$ by adding a new vertex $w$ and $k$ new edges, namely $(w, v_1)$, $(w, v_2)$, $\cdots$ and $(w, v_k)$, to $G$. It is easy to know that $G'$ is $k$-edge connected. By Menger's theorem, there exists $k$ edge-disjoint paths from $v$ to $w$. If we remove $w$ from each of these paths, the paths are from $v$ to each $v_i$ in $G$ and are edge-disjoint.
Best Answer
Assuming that the "paths" we're talking about are actually trails, that is, walks that may repeat vertices but may not repeat edges (which seems to be the most natural context for requiring them to be edge-disjoint), that sounds right to me.
Clearly at least that many paths will be needed, and it's not too difficult to see that you can construct a covering at set of exactly that many paths greedily:
Start at an odd-degree vertex, and walk along random unused edges until you there's nowhere you can go. At that time you must have reached another odd degree vertex.
Continue doing this as long as there are odd-degree vertices left.
If there are still unused edges in the graph, locate a vertex that is touched by both used and unused edges. Break one of the paths you have already identified through that vertex, and start walking randomly along unused edges from there. Since you've used up all of the odd vertices, the only place you can end is at the vertex where you started, so you can then proceed along the rest of the original path, so the number of paths doesn't increase.
Repeat until all edges have been covered.