Let G be a graph of maximum degree ∆. Show that it is possible to assign integers to all edges of G in such a way that any path P = $v_1...v_l$ in which the integer assigned to edge $v_i v_{i+1}$ is not larger than the one assigned to edge $v_{i+1} v_{i+2}$ for all $i < l-1$ has length as most $\Delta + 1$.
In other words we want to assign 'edge weights', so that any path with monotonically increasing 'edge weights' has length at most $\Delta + 1$.
My first guess was to just take a longest path and then either assign integers 1 through $\Delta$ (consecutively and then count down again to 1 and then count up again, etc) or integers 0 and 1 alternating. These two option don't violate what we want, but I dont see how one would proceed from there (after deleting that path). Induction with this method doesn't work I think, since the max degree does not have to decrease after deleting a maximum length path. In fact, there may not even be a path of maximum length that uses any vertex of maximum degree.
Another guess would be to use probabilistic method and just assign integers randomly (although here I don't know how many integers we would need, natural guesses could be $\{1,..., \Delta\}$, $\{1,..., \Delta + 1\}$ or $\{1,..., |E|\}$) and then look at the probability of $\Delta + 1$ monotonically increasing integers appearing.
Thankful for any suggestions, questions or answers on the problem.
$\endgroup$ 1 Reset to default
