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$
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 '18 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$ – Misha Lavrov Feb 18 '18 at 22:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.