graph theory
Given a directed graph $G$ such that $\text{indeg}_{G}(x)$ and $\text{outdeg}_{G}(x)$ have the same parity for all $x \in V(G)$. Let $$X = \{x \in V(G) : \text{outdeg}(x) – \text{indeg}(x) > 0 \}$$ and $$Y = \{y \in V(G) : \text{indeg}(x) – \text{outdeg}(x) > 0 \}$$
Show that $G$ can be decomposed into a set $\mathcal{D}$ of pairwise edge-disjoint directed cycles and directed paths such that each directed path emanates from a vertex in $X$ and terminates at a vertex in $Y$.
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.
Your proof would be absolutely fine if we can prove that the construction of a simple edge disjoint cycle is always possible. Take any vertex u with a positive degree and start a tour on adjacent vertices until you are unable to explore further. Keep deleting the edges you have traveled. Assume you end at vertex v. What we have is a trail (not path): $$u,u_{1},u_{2}........v$$ The claim is, v has to be u.
Assume u and v are different. For every appearance of vertex v except the last one in the above list, there need to be two edges incident on v, one incoming and other outgoing. But for the last appearance, we need only one edge to enter the vertex v. Hence odd number of edges incident on v are used in the above trail. This leads to the fact there is at least one more edge on v yet to be explored. So the vertex v can not be the end of traversal. This proves u=v.
Now we have the circuit, which can be broken into disjoint edge cycles. How? For every two occurrence of a vertex y in the circuit, remove the circuit y-y from the parent circuit. Keep doing this recursively to get cycles.
Example: circuit $u,u_{1},u_{2},u_{3},u_{2},u$ be broken into $u,u_{1},u_{2},u$ and $u_{2},u_{3},u_{2}$
Since we have deleted the edges explored, the cycles have disjoint edges. We recursively keep finding circuits in the main graph, deleting the edges until we have explored all the edges. Which completes your proof.
An easy proof- let $G_{1}$,$G_{2}$,$G_{3}$... be connected components of the graph. Since the degree of each vertex is even there are Eulerian circuit for each component. Then the trails can be broken into disjoint cycles for each component.
Best Answer
Hints:
I hope this helps ;-)