graph theory
I do not know how to solve this exercise:
Let $G(V,E)$ be a simple undirected graph with $\lvert V(G)\rvert \ge 2$ and $deg(v) \ge k$ for all $v \in V(G)$. Show that there are two nodes $s$ and $t$ in $G$ such that $s$ and $t$ are connected by at least $k$ edge-disjoint paths. Is the claim also true if $G$ has exactly one node $w$ with $deg(w) < k$.
We have recently done Gomory-Hu trees in class, so I suppose this should be used here, but I do not see how. Could you give me a hint?
I'm going to disagree with the answers so far and say that the result is false.
Not only is it false, but no graph satisfying all the conditions can possibly have two such trails.
Below is an expertly drawn 2-edge connected graph with exactly two odd vertices $u,v$. It's clearly not possible to cover all the edges with exactly two edge-disjoint trails from $u$ to $v$. You can do it with one trail or three trails, but not two trails.
But why is it never true?
Say that we have a trail from $u$ to $v$. Remove it. All the vertices will now have even degree, so any trail that uses all the edges must end up where it started and so can't be a trail from $u$ to $v$.
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.
Best Answer
By Menger's theorem, your problem is equivalent to finding two vertices $s$ and $t$ such that the size $\lambda_{s,t}$ of a minimum $s-t$ cut is at least $k$. Let $s$ be a leaf in a Gomory-Hu tree of $G$ and let $t$ be its unique neighbour in the tree. Then by the properties of Gomory-Hu trees, $\lambda_{s,t}$ is the number of edges crossing the cut $(\{s\}, V-\{s\})$; but this is just $\deg(s) \geq k$.
Since a tree has at least two leaves, the same proof works in the case when there is a single vertex with degree less than $k$.