Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.