1
$\begingroup$

I have the following definition of 2-sum of two graphs:

Suppose $G_1,G_2$ are graphs on at least three vertices such that $$V(G_1)\cap V(G_2)=\{u,v\}$$ and $E(G_1)\cap E(G_2)$ consists of a single edge joining $u$ to $v$. Then, the 2-sum of $G_2,G_2$ with respect to the pair $(u,v)$ is the graph with vertex set $V(G_1)\cup V(G_1)$ and edge set $$E(G_1)\oplus E(G_2)$$ where $\oplus$ denotes symmetric difference.

Question: Why is the 2-sum of two cycles a cycle and not two cycles? If $G_1,G_2$ are each a cycle with $u,v\in V(G_1)\cap V(G_2)$ and $e:=uv \in E(G_1)\cap E(G_2)$, then shouldn't the 2-sum of the two cycles be $G_1$ and $G_2$ with the edge $e$ removed which is two cycles?

$\endgroup$

1 Answer 1

3
$\begingroup$

If we're taking the $2$-sum of two cycles, the two graphs look like this:

two-cycles

The red edges (and the shared purple edge) form the first cycle, and the blue edges (and the shared purple edge) form the second cycle.

The symmetric difference $E(G_1) \oplus E(G_2)$ will include the red edges (which are part of $E(G_1)$ but not $E(G_2)$) and the blue edges (which part part of $E(G_2)$ but not $E(G_1)$) but not the purple edge (which is in both). So the $2$-sum of the graphs will be

2-sum

which is a single cycle.

$\endgroup$
2
  • 2
    $\begingroup$ Can you tell me the secret of how you made those pictures? $\endgroup$
    – mike239x
    Feb 18, 2018 at 22:43
  • 3
    $\begingroup$ @mike239x Mathematica. I still have the source code for the second picture: p = CirclePoints[{1, Pi/6}, 6]; q = ({Sqrt[3], 0} - #) & /@ p; Graphics[{Black, Line[p], Line[q], PointSize[0.02], Point[p], Point[q]}]. I don't have the source code for the first, since I edited it to turn into the second. $\endgroup$ Feb 18, 2018 at 22:45

You must log in to answer this question.

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