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$
    – bor
    Commented Feb 28, 2014 at 8:05

1 Answer 1

1
$\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$
    – nvcleemp
    Commented Jun 1, 2014 at 19:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .