Eulerian Circuit-Cycle Decompositions

371 Views Asked by At

For some background information, Eulerian here refers to starting and ending on the same vertex (i.e. being closed).

Also, the corollary below uses Theorem 3.4 which states a graph is Eulerian iff each edge lies on an odd number of cycles.

$\textbf{Question:}$ What is the reason that $s(G)\equiv \displaystyle\sum_{i=1}^rs_i$ holds true at the very bottom of the proof below?

enter image description here

This corollary is found on page 68 here.

Note I do understand the following in the proof:

$\text{ Set of All Cycle Decompositions of G}=\{\text{Every Cycle Decomposition of } G_i \cup C_i\}_{i=1, 2, ..., r}$

and that $s_i=|\text{Every Cycle Decomposition of } G_i \cup C_i |$ in consideration as to what is inside the set above.

At a glance, $s(G)=\displaystyle \sum_{i=1}^r s_i$ holds true by simply adding up each cycle decomposition at a time to get the total number.

However, wouldn't there be a chance that a cycle decomposition of $G_i$ $\cup C_i$ might be equal to a cycle decomposition of $G_j\cup C_j$ where $i\neq j$ which seems like a problem.

1

There are 1 best solutions below

2
On BEST ANSWER

The problem that concerns you would arise only if $C_i$ appeared in a cycle decomposition of $G_j$ for some $j\ne i$. This cannot happen, however, because $C_i$ and $C_j$ both contain the edge $e$ chosen at the start of the proof: no cycle in a cycle decomposition of $C_j$ can contain $e$, since it belongs to $C_j$, and therefore no cycle in a cycle decomposition of $G_j$ can be $C_i$, which also contains $e$.