The Lovász Path Removal Conjecture states:

For any positive integer $k$, there exists a minimum positive integer $f(k)$ such that, for any two vertices $x$, $y$ in any $f(k)$-vertex-connected graph $G$, there is an $x$-$y$ path $P$ in $G$ such that $G\backslash P$ is $k$-vertex-connected.

It is commonly stated that $ f(1)=3 $ due to a theorem in Tutte's paper "How to draw a graph" (Proc. London Math. Soc. 13.3 (1963), 743–768).

However, I can't find any theorem in Tutte's paper that directly states that a 3-vertex-connected graph contains a non-separating path between any two vertices. Can someone point out to me the relevant theorem in Tutte's paper and show how it implies the above fact?

  • $\begingroup$ Currently the question has votes to close as "unclear what is being asked". I think it is reasonably clear what is being asked: the OP wants to know which theorem in Tutte's paper states and proves the result mentioned in her first paragraph $\endgroup$ – Yemon Choi Mar 26 '15 at 19:11
  • 1
    $\begingroup$ I edited the question to clarify it. $\endgroup$ – Timothy Chow Mar 26 '15 at 20:51
  • 2
    $\begingroup$ I also think it is clear what is being asked. Note that Tutte's papers can be difficult to read (partly due to clashes with modern terminology), but the payoff is usually well worth it. For a more modern account of the paper How to draw a graph see math.uwaterloo.ca/~jfgeelen/Publications/tutte.pdf $\endgroup$ – Tony Huynh Mar 26 '15 at 21:51

Tutte in that paper shows that if the connectivity of a graph is at least 3, then for any two distinct vertices in that graph, there exists a non-separating path between them. Any cycle plus a single chord shows $f(1) \geq 3$ and Tutte's Wheel Theorem shows that $f(1) \leq3$. Thus, $f(1)=3$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.