3
$\begingroup$

Let $G$ is a finite simple undirected graph. Suppose there exist subgraph $G_1,G_2,\dots,G_n$ of $G$, such that $G_i \cong K_5$ or $K_{3,3}$, $E(G_i)\cap E(G_j) = \emptyset$ and $|V(G_i)\cap V(G_j)| \leq 3$, for $i\neq j$. Then, is it true that genus of $G$ is greater than or equal to $n$?

Thanks in advance.

$\endgroup$
0

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Suppose $K_{11}$ has 6 subgraph $G_i,1 \leq i \leq 6$, such that $G_i \cong K_5$ and $E(G_i)\cap E(G_j) = \emptyset, i\neq j$. Then $55 = |E(G)| \geq \underset{i=1}{\overset{6}\sum} |E(G_i)| =60$, which is not possible. So i think your counter example does't work, or may be i miss the point. $\endgroup$ Commented Feb 10, 2014 at 7:44
  • $\begingroup$ @bor The K_11 example might indeed be wrong, let me try to fix it if possible at all... $\endgroup$ Commented Feb 10, 2014 at 7:52
  • $\begingroup$ @bor I suggest K_{6,3} as counterexample, genus 1, explicit subgraphs. $\endgroup$ Commented Feb 10, 2014 at 9:25

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.