# Largest independent Set of $C_n$

I see that:

For a cycle graph $n\ge3$, $C_3$ has $1$ independent set, $C_4$ has $2$ independent set, $C_5$ s set, $C_6$ $3$ set, $C_7$ $3$ set, $C_8$ $4$ set, $C_9$ $4$ set.

I can't show this trend as an equation or a mathematic expression. Is it possible to show in one?

-

I assume that ‘s’ is a typo for $2$ as the size of a maximal independent set in $C_5$.

If $i(n)$ is the maximal size of an independent set of vertices in $C_n$, you have:

$$\begin{array}{rcc} n:&3&4&5&6&7&8&9\\ i(n):&1&2&2&3&3&4&4 \end{array}$$

You can express this in many ways. The most straightforward is simply to use a two-part definition:

$$i(n)=\begin{cases}\frac{n}2,&\text{if }n\text{ is even}\\\\ \frac{n-1}2,&\text{if }n\text{ is odd}\;.\end{cases}$$

If you know the floor function, also called the greatest integer function, you can simply write

$$i(n)=\left\lfloor\frac{n}2\right\rfloor\;.$$

Other ways are more complicated. For instance, you can easily check that

$$i(n)=\frac12\left(n-\frac{1-(-1)^n}2\right)$$

gives the same result as the two-part definition, though I don’t recommend using this form!

-
This makes a lot sense than my class notes. I do not know the floor function. Is it common function to use for discrete mathematics? –  Uka Nov 7 '12 at 3:24
@Uka: Yes, definitely; so is the ceiling function. This article is a pretty decent introduction to both of them. –  Brian M. Scott Nov 7 '12 at 3:26
Thank you for the link and your help! –  Uka Nov 7 '12 at 3:31
@Uka: You’re very welcome! –  Brian M. Scott Nov 7 '12 at 3:34