# Non-toroidality of a simple graph

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

• Where do the options come from? Commented Feb 28, 2014 at 7:49
• 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.
– bor
Commented Feb 28, 2014 at 8:05

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.

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]}

• you are of course right. ;-) Fixed that! Commented Jun 1, 2014 at 19:04