1
$\begingroup$

Let $G$ be a simple undirected graph and $G_1$ and $G_2$ are two subgraphs of $G$, with $E(G_1) \cap E(G_2) =\emptyset$. Which of the following conditions would imply that $G$ is not toroidal:

a; $G_1 \cong K_{3,3}$, $G_2 \cong K_5$, $|V(G_1)\cap V(G_2)| \leq 2$.

b; $G_1, G_2 \cong K_{3,3}$, $|V(G_1)\cap V(G_2)| \leq 2$.

c; $G_1, G_2 \cong K_{3,3}$, $|V(G_1)\cap V(G_2)| \leq 3$ and $K_{6,3}$ is not a subgraph of $G$.

Thanks in advance.

$\endgroup$
2
  • $\begingroup$ Where do the options come from? $\endgroup$ Commented Feb 28, 2014 at 7:49
  • $\begingroup$ After series of studying graph theory, I came across certain graph with one of the above condition, and I could not conclude whether they are toroidal or not. $\endgroup$ Commented Feb 28, 2014 at 8:05

1 Answer 1

2
$\begingroup$

None of these condition imply that G is not toroidal. My example in Additivity of genus show that conditions b and c do not imply this. The graph below has genus 1, and thus shows that condition a does not imply this.

A union of $K_5$ and $K_{3,3}$ with genus 1.

The following embedding corresponds to genus 1:

{0: [1, 3, 4, 8, 5, 6, 7], 1: [0, 7, 8, 4, 6, 5, 3], 2: [3, 5, 4], 3: [0, 1, 2], 4: [0, 2, 1], 5: [0, 2, 1], 6: [0, 1, 8, 7], 7: [0, 6, 8, 1], 8: [0, 1, 7, 6]} 
$\endgroup$
1
  • $\begingroup$ you are of course right. ;-) Fixed that! $\endgroup$ Commented Jun 1, 2014 at 19:04

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.