Skip to main content
3 of 3
3-connected counterexample
joro
  • 25.4k
  • 10
  • 66
  • 121

I believe this is false.

EDIT

The previous counterexample was wrong, let me try again.

A program found counterexample on $10$ vertices and exhaustive search confirmed it.

The edges are:

[(0, 3), (0, 5), (0, 7), (1, 4), (1, 6), (1, 9), (2, 6), (2, 7), (2, 8), (3, 5), (3, 7), (4, 8), (4, 9), (5, 8), (6, 9)]

It is $2$-connected.


According to a search the smallest $3$-connected counterexample is on $12$ vertices with edges

[(0, 6), (0, 7), (0, 8), (1, 6), (1, 7), (1, 9), (2, 6), (2, 10), (2, 11), (3, 7), (3, 10), (3, 11), (4, 8), (4, 9), (4, 10), (5, 8), (5, 9), (5, 11)]

There are other counterexamples (modulo errors).

joro
  • 25.4k
  • 10
  • 66
  • 121