In my HW assignments I was asked to prove that If a graph G consists of only odd degree vertices, then the minimum number of trails that decompose it (without having any common edge between each two trails) is n/2.
I saw a prove for a similar claim that goes for a 2k number of odd vertices. obviously since every graph contains an even number of degrees, then the number of vertices is even so that goes for proving there exist n/2 paths in the graph G , the only thing that is missing for me is to understand why is this the minimum number of trails.
The prove of the other claim is here: Prove that there exists a set of $k$ edge-disjoint walks that cover a graph with $2k$ odd-degree vertices?
I thank in advance to any one who answers:)
Assuming $n$ is the order of $G$, then $n$ must be even by the Handshake Lemma. If you add a vertex $v$ and then connect it to all the vertices in $G$, you will create an Eulerian graph $G+v$. If you start the Eulerian circuit at $v$, then you must go to some vertex in $G$ and travel along a trail in $G$ and return to $v$. You will do this $n/2$ times, each time choosing a different edge disjoint trail in $G$. Then delete $v$ and you will have your desired decomposition of $G$.