1
$\begingroup$

I am seeking advice on how to prove something. Apologies if my terminology is incorrect: I am not a mathematician.

Let $G_1$ and $G_2$ be undirected cycle graphs with edges $E_{G1}$ and $E_{G2}$ respectively.

Let $e_{G1} = (a,b)$ and $e_{G2} = (x,y)$ be arbitrary edges from $E_{G1}$ and $E_{G2}$ respectively.

Remove these edges from their respective graphs.

For every edge in $G_1$, substitute $a$ for $x$ and $b$ for $y$.

Let $G_3 = G_1 \cup G_2$.

$G_3$ is a undirected cycle graph.

I would like to prove this, but I have literally no idea how to do this. Can anyone offer any advice?

Thanks

$\endgroup$
1
  • $\begingroup$ To formalize this, I would say consider two cycle graphs, and prove that $E(G_{1}) \triangle E(G_{2})$ is a cycle, where $\triangle$ is the symmetric difference operator. You're trying to prove this anyways, and it makes the problem statement clearer. $\endgroup$
    – ml0105
    Commented Apr 10, 2014 at 20:44

1 Answer 1

2
$\begingroup$

This is the type of result that's much easier to intuit than it is to rigorously prove. For a rigorous proof, it's probably best to enumerate the vertices and edges of each graph:

Let $G_1$ and $G_2$ be cycles with:

$$V(G_1)=\{u_1, u_2, \dots, u_{m}\}$$

$$E(G_1) = \{u_1 u_2, u_2 u_3, \dots, u_{m-1} u_{m}, u_{m} u_1\}$$

$$V(G_2)=\{v_1, v_2, \dots, v_{n}\}$$

$$E(G_2) = \{v_1 v_2, v_2 v_3, \dots,v_{n-1} v_{n},v_{n} v_1\}$$

You may assume that the edge to be deleted from $G_1$ is $u_m u_1$, and the edge to be deleted from $G_2$ is $v_1 v_n$ because of symmetry (otherwise you could relabel the vertices to make it so). Then the graph $G$ obtained by deleting $u_m u_1$ from $G_1$ and $v_n v_1$ from $G_2$ and identifying vertex $u_1$ with vertex $v_n$ (calling the new vertex $u_1$) and vertex $u_m$ with vertex $v_1$ (calling the new vertex $u_m$) is the graph you are looking for. Now we have:

$$V(G) = \{u_1, u_2, \dots, u_m, v_2, v_3, \dots, v_{n-1}\}$$

$$E(G) = \{u_1 u_2, u_2 u_3, \dots, u_{m-1} u_m, u_m v_2, v_2 v_3, v_3 v_4, \dots, v_{n-2} v_{n-1}, v_{n-1} u_1\}$$

But this is exactly a cycle on $m+n-2$ vertices.

$\endgroup$
2
  • $\begingroup$ @perry-inverson is it sufficient to just say "But this is exactly a cycle on m+n−2 vertices"? This is the part that I am confused about. $\endgroup$
    – S0rin
    Commented Apr 14, 2014 at 17:18
  • $\begingroup$ Yes I would say so. Notice that when we knew $G_1$ was a cycle, we could assume $V(G_1) = \{u_1, u_2, \dots, u_m\}$, and $E(G_1) = \{u_1 u_2, u_2 u_3, \dots, u_{m-1} u_m, u_m u_1\}$. Then notice that what we end up with for $V(G)$ and $E(G)$ is exactly this same format, with $m+n-2$ vertices total. If you relabel $v_2$ as $u_{m+1}$, $v_3$ as $u_{m+2}$, $\dots$, $v_{n-1}$ as $u_{m+n-2}$, then it will be even more clear that the edge list is exactly the same format. $\endgroup$ Commented Apr 14, 2014 at 17:31

You must log in to answer this question.

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