Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I need some help to see if the definition I found of Cycles and Cycles Decomposition is right, here it is:

A graph is a Cycle if it is isomorph to another graph $G=(V,E)$ with the following proprieties: $V=\{v_0,v_1,\ldots,v_m\}$ and $(v_i,v_j)\in E$ if and only if $|i-j|=1$ or $|i-j|=m$.

A graph is Decomposible in Cycles if it is an Edge-disjoint union of Cycles

This bring me to see the graph $C_2=(V,E)$, $V=\{v_0,v_1\}$, $E=\{(v_0,v_1)\}$ (the simple "dot-line-dot" graph) as Cycle, but if it is then every graph can be decomposed in a series of $C_2$ Cycles.

(I aplogize both for the english, definition are actually translated form french, and for the bad formatting)

If someone know a better definition or see where the error is in my conclusion it would be helpfull.

Thanks, Midkar.

share|cite|improve this question
The definition is slightly defective. If you add the condition $m\ge 2$ you get a correct definition; alternatively, you can add the condition $\deg(v)=2$ for each $v\in V$. –  Brian M. Scott Dec 27 '12 at 15:30
Here is an introduction to writing mathematics here. (And don’t worry about the English: it’s perfectly understandable. I’ve noticed that it usually is when people apologize for it!) –  Brian M. Scott Dec 27 '12 at 15:34
Thanks for the math Thomas, but are you sure aboute the m≥2 condition? Is not also C0=(V,E), V={v0}, E={} a Cycle? Deg(v)=2 for a Cycle is a theorem in the conception of my course, so I dont think I can use it in the definition. Does anyone know a different definition? (I'm apart from my math libray and I cant find out from myself a statisfying one on the internet) –  midakr Dec 27 '12 at 15:46
The one-point graph with no edges isn’t a cycle by the definitions that I know. Douglas West’s text requires a cycle to have the same number of edges and vertices. Reinhard Diestel’s text requires $m\ge 2$. Either condition rules out your $C_0$ and $C_2$. –  Brian M. Scott Dec 27 '12 at 15:51
It seems that my text consider C0 (I notice that I should have called it C1) a Cycle in many induction demonstrations (but they can be done easily with a G with girth 3 instead of C0), but I think that a "A Cycle is a Connected Graph whit|V| = |E|" (whit maybe the exception |V|=1 |E|=0 for C0) will do. Thanks you for the help! –  midakr Dec 27 '12 at 16:10

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.