4
$\begingroup$

Tutte (1961): A graph $G$ is $3$-connected if and only if there exists a sequence $G_0, ...,G_n$ of graphs that have the following two properties

1) $G_0 = K_4$ and $G_n = G$

2) $G_{i+1}$ has an edge $xy$ with $d(x), d(y) ≥ 3$ and $G_i = G_{i+1}/xy$.

(If $G$ is a graph, the graph $G'$ obtained by an edge contraction of an edge $xy$ is denoted $G/xy$.)

My questions:

  1. How to construct the sequence?

(It seems that according to 2), we can construct by the reduction from $G_n$, however, it may can't make sure that in the final stage we can get $G_0=K_4$.)

  1. How to extend it to $k$-connected graph (where $k$>3)?

Reference:

[1] R. Diestel, Graph Theory, third ed., Springer-Verlag, 2005

$\endgroup$
1
  • $\begingroup$ Lovász Path Removal Conjecture: There exists a function $f=f(k)$ such that the following holds. For every $f(k)$-connected graph $G$ and two vertices $s$ and $t$ in $G$, there exists a path $P$ with endpoints $s$ and $t$ such that $G-V(P)$ is $k$-connected. My motivation of the question 2 is that whether the similar method can be applied to the general case of Lovász Path Removal Conjecture. $\endgroup$
    – user39815
    Mar 15, 2014 at 20:18

1 Answer 1

3
$\begingroup$

Tutte proved that every 3-connected graph with at least 5 vertices has an edge whose contraction leaves a 3-connected graph. So starting with $G_n$, just keep contracting suitable edges until you reach $K_4$. It is the unique 3-connected graph with less than 5 vertices, so there is no way to avoid it.

Search at Scholar for "contractible edge" to find much more on this subject, including lots of papers about generalizations to $k$-connectivity.

$\endgroup$
1
  • $\begingroup$ thank you very much for your helpful answer! In this paper google.com/… Based on the idea of your answer of question one, the author proved that $f(3)=6$ of Lovász Path Removal Conjecture. $\endgroup$
    – user39815
    Mar 15, 2014 at 20:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.