5
$\begingroup$

Let $G$ be a 3-connected (simple) graph other than $K_4$. In Diestel's "Graph Theory" Section 3.2 we find

  • Lemma 3.2.2. There is an edge $e$ so that $G\mathbin{\dot-}e$ is still 3-connected (where $G\mathbin{\dot-}e$ means deleting $e$ and supressing resulting vertices of degree 2).
  • Lemma 3.2.4. There is an edge $e$ so that $G/e$ is still 3-connected (where $G/e$ means contracting $e$ and replacing resulting double edges by a single edge).

I wonder, can we always find an edge $e$ so that both $G\mathbin{\dot-}e$ and $G/e$ are still 3-connected? Is it true at least if $G$ is planar?

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ You can also create degree-2 vertices when you contract an edge. For example, in a triangular prism, contracting an edge from a triangle creates a degree-2 vertex (after suppressing parallel edges). In fact, the triangular prism is a counterexample, given your definitions of $G -e$ and $G / e$. Maybe you also want to supress degree-2 vertices when contracting? $\endgroup$
    – Tony Huynh
    Commented Feb 12 at 23:01
  • 2
    $\begingroup$ @TonyHuynh You are right, and supressing degree-2 vertices after a deletion can create double edges. So I think what I want is to "iteratively normalize" the graph after a deletion/contraction so as to not contain degree-2 vertices or double edges. Your answer provides sufficient counterexample still. $\endgroup$
    – M. Winter
    Commented Feb 13 at 12:37

1 Answer 1

Reset to default
8
$\begingroup$

No, this is false even in the planar case. Let $G=W_n$ be a wheel graph with $n \geq 6$. Deleting any edge of the outercycle yields a fan graph, which is not $3$-connected. On the other hand, contracting any edge which is not on the outercycle also yields a fan graph. Thus, there is no edge $e$ such that $G - e$ and $G / e$ are both $3$-connected.

Improve this answer
$\endgroup$

You must log in to answer this question.

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