Skip to main content
Added K_{3,3n}
Source Link
joro
  • 25.4k
  • 10
  • 66
  • 121

Second try. I believe $K_{6,3}$ is a counterexample.

It is genus $1$ and contains $2$ edge disjoint $K_{3,3}$s sharing only $3$ vertices.

Explicitly:

K_{6,3}=[(0, 6), (0, 7), (0, 8), (1, 6), (1, 7), (1, 8), (2, 6), (2, 7), (2, 8), (3, 6), (3, 7), (3, 8), (4, 6), (4, 7), (4, 8), (5, 6), (5, 7), (5, 8)]
first K_{3,3}=[(3, 6), (3, 7), (3, 8), (4, 6), (4, 7), (4, 8), (5, 6), (5, 7), (5, 8)]
second K_{3,3}=[(0, 6), (0, 7), (0, 8), (1, 6), (1, 7), (1, 8), (2, 6), (2, 7), (2, 8)]
shared vertices 8,6,7

Added $K_{3,3n}$ are counterexamples too.

$g(K_{3,3n})=\lceil (3n-2)/4 \rceil < (3n-2) / 4 + 1$

$K_{3,3n}$ has $n$ disjoint $K_{3,3}$ sharing only $3$ vertices: connect the $3$ partition to $3$ distinct vertices from the $3n$ partition.

Second try. I believe $K_{6,3}$ is a counterexample.

It is genus $1$ and contains $2$ edge disjoint $K_{3,3}$s sharing only $3$ vertices.

Explicitly:

K_{6,3}=[(0, 6), (0, 7), (0, 8), (1, 6), (1, 7), (1, 8), (2, 6), (2, 7), (2, 8), (3, 6), (3, 7), (3, 8), (4, 6), (4, 7), (4, 8), (5, 6), (5, 7), (5, 8)]
first K_{3,3}=[(3, 6), (3, 7), (3, 8), (4, 6), (4, 7), (4, 8), (5, 6), (5, 7), (5, 8)]
second K_{3,3}=[(0, 6), (0, 7), (0, 8), (1, 6), (1, 7), (1, 8), (2, 6), (2, 7), (2, 8)]
shared vertices 8,6,7

Second try. I believe $K_{6,3}$ is a counterexample.

It is genus $1$ and contains $2$ edge disjoint $K_{3,3}$s sharing only $3$ vertices.

Explicitly:

K_{6,3}=[(0, 6), (0, 7), (0, 8), (1, 6), (1, 7), (1, 8), (2, 6), (2, 7), (2, 8), (3, 6), (3, 7), (3, 8), (4, 6), (4, 7), (4, 8), (5, 6), (5, 7), (5, 8)]
first K_{3,3}=[(3, 6), (3, 7), (3, 8), (4, 6), (4, 7), (4, 8), (5, 6), (5, 7), (5, 8)]
second K_{3,3}=[(0, 6), (0, 7), (0, 8), (1, 6), (1, 7), (1, 8), (2, 6), (2, 7), (2, 8)]
shared vertices 8,6,7

Added $K_{3,3n}$ are counterexamples too.

$g(K_{3,3n})=\lceil (3n-2)/4 \rceil < (3n-2) / 4 + 1$

$K_{3,3n}$ has $n$ disjoint $K_{3,3}$ sharing only $3$ vertices: connect the $3$ partition to $3$ distinct vertices from the $3n$ partition.

Post Undeleted by joro
Second try with K_{6,3}$
Source Link
joro
  • 25.4k
  • 10
  • 66
  • 121

Second try. I believe $K_{11}$$K_{6,3}$ is a counterexample (and possibly $K_n$ for $n \ge 11$).

The genus of $K_{11}$It is genus $5$$1$ and it has morecontains $K_5$'s even vertex$2$ edge disjoint $K_{3,3}$s sharing only satisfying your constraints$3$ vertices.

Explicitly:

K_{6,3}=[(0, 6), (0, 7), (0, 8), (1, 6), (1, 7), (1, 8), (2, 6), (2, 7), (2, 8), (3, 6), (3, 7), (3, 8), (4, 6), (4, 7), (4, 8), (5, 6), (5, 7), (5, 8)]
first K_{3,3}=[(3, 6), (3, 7), (3, 8), (4, 6), (4, 7), (4, 8), (5, 6), (5, 7), (5, 8)]
second K_{3,3}=[(0, 6), (0, 7), (0, 8), (1, 6), (1, 7), (1, 8), (2, 6), (2, 7), (2, 8)]
shared vertices 8,6,7

I believe $K_{11}$ is a counterexample (and possibly $K_n$ for $n \ge 11$).

The genus of $K_{11}$ is $5$ and it has more $K_5$'s even vertex disjoint satisfying your constraints.

Second try. I believe $K_{6,3}$ is a counterexample.

It is genus $1$ and contains $2$ edge disjoint $K_{3,3}$s sharing only $3$ vertices.

Explicitly:

K_{6,3}=[(0, 6), (0, 7), (0, 8), (1, 6), (1, 7), (1, 8), (2, 6), (2, 7), (2, 8), (3, 6), (3, 7), (3, 8), (4, 6), (4, 7), (4, 8), (5, 6), (5, 7), (5, 8)]
first K_{3,3}=[(3, 6), (3, 7), (3, 8), (4, 6), (4, 7), (4, 8), (5, 6), (5, 7), (5, 8)]
second K_{3,3}=[(0, 6), (0, 7), (0, 8), (1, 6), (1, 7), (1, 8), (2, 6), (2, 7), (2, 8)]
shared vertices 8,6,7
Post Deleted by joro
added 28 characters in body
Source Link
joro
  • 25.4k
  • 10
  • 66
  • 121

I believe $K_{11}$ is a counterexample (and possibly $K_n$ for $n \ge 11$).

The genus of $K_{11}$ is $5$ and isit has more $K_5$s's even vertex disjoint satisfying your constraints.

I believe $K_{11}$ is a counterexample (and possibly $K_n$ for $n \ge 11$).

The genus of $K_{11}$ is $5$ and is has more $K_5$s even vertex disjoint.

I believe $K_{11}$ is a counterexample (and possibly $K_n$ for $n \ge 11$).

The genus of $K_{11}$ is $5$ and it has more $K_5$'s even vertex disjoint satisfying your constraints.

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