Given a complete graph with n vertices such that all edge weights are distinct. Prove that we can find a monotonically increasing path of length n-1.
I tried finding such a path by sorting the edges in increasing weight and then greedily selecting such that they make up a path. eg: Lets consider a graph where $w_{a,b}=1, w_{a,c}=2, w_{a,d}=3, w_{b,c}=4, w_{b,d}=5, w_{c,d}=6$. I first select a->b. Then we find the next edge which starts from b and has the least weight. We get b->c. And so on. The path I get is : a->b->c->d. But I'm not able to prove that this will always work. Any suggestions?
I think the problem is similar to Counting certain paths in a complete graph.
1 Answer
I figured I should make my comments an answer.
I found the following in an old paper of Graham and Kleitman ("Increasing Paths in Edge Ordered Graphs," Periodica Mathematica Hungarica Vol 3 (1973)).
If by "path" you allow repeated vertices (what is often called a trail these days), then their Theorem 1 easily implies what you want (just relabel your edge weights by putting 1 to your least edge weight, 2 as your second least edge weight etc).
If by "path" you mean no repeated vertices (what they call "simple path"), then the answer to your question is no, and here is a counterexample derived from their Section IV. Consider $K_{4}$ with vertices $a,b,c,d$, and edge weights: $w_{a,b}=1$, $w_{b,c}=6$,$w_{c,d}=2$, $w_{d,a}=5$, $w_{b,d}=4$, $w_{a,c}=3$.
PS I just realized bof's example is also a counterexample.
