Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

What should the base case be for an induction proof on a general property for Cn, cycle graphs?

Would it be n=2 or n=3? Since n=2 is not a simple graph, I'm guessing it would be the cycle graph on n=3 vertices?

share|cite|improve this question
Yes, there's no cycle graph on 2 vertices, so you'd better start with a triangle. – MJD Feb 19 '13 at 3:16
Awesome thanks! – DJ_ Feb 19 '13 at 3:17
up vote 3 down vote accepted

For the proof to be meaningful, as you suggest, you'd need a base case $n = 3$ vertices, as the minimum number of vertices required for a graph to be a cycle is $3$

share|cite|improve this answer

Your Answer


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

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