9
$\begingroup$

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?

$\endgroup$
3
  • $\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
    Commented Mar 26, 2015 at 19:11
  • 1
    $\begingroup$ I edited the question to clarify it. $\endgroup$ Commented Mar 26, 2015 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
    Commented Mar 26, 2015 at 21:51

1 Answer 1

3
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .