Skip to main content
3-connected counterexample
Source Link
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).

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.

There are other counterexamples (modulo errors).

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

Tried to correct the answer with another counterexamples
Source Link
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 $8$$10$ vertices and exhaustive search confirmed it.

The edges are:

[(0, 43), (0, 5), (0, 67), (1, 4), (1, 56), (1, 79), (2, 46), (2, 67), (2, 78), (3, 5), (3, 67), (34, 78), (4, 9), (5, 8), (6, 9)]

It is $3$$2$-connected.

There are other counterexamples (modulo errors).

I believe this is false.

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

The edges are:

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

It is $3$-connected.

There are other counterexamples (modulo errors).

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.

There are other counterexamples (modulo errors).

Source Link
joro
  • 25.4k
  • 10
  • 66
  • 121

I believe this is false.

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

The edges are:

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

It is $3$-connected.

There are other counterexamples (modulo errors).