# Graph Walk on Monotonic Sequence

Given an undirected connected graph with $E$ edges, arbitrarily each edge with a unique number between 1 and $|E|$.

Show that there exists a path with monotone labels whose length is at least the average degree of the graph.

Ideas: in order to show that at least one path exists we can start traversing from every vertex, however there are should be two types of traversing in increasing order and in decreasing order.

As a result of traversing we should show that at least one of them counted at least average degree edges.

-
The reader may be interested in this forum post which matches first part of the question posted here. The forum thread also has a hint and an attempted answer. – Douglas S. Stones Mar 27 '13 at 15:31
@DouglasS.Stones, thank you very much for the link, unfortunately the hint is very ambiguous for me. Could you please elaborate about it. – fog Mar 29 '13 at 9:53
It's vague for me also (but, presumably there's something important I'm missing). I posted the link in case it helps someone else answer the question. – Douglas S. Stones Mar 29 '13 at 12:37