Take the 2-minute tour ×
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.

For which $n$ from $N$ is $C_{n}$ isomorphic to its complement?

Blew my mind, I mean is there even one? I've been trying to find at least one, but I wasn't lucky and I can't even imagine such a thing. Help please, any hint is appreciated.

share|improve this question
add comment

1 Answer

up vote 3 down vote accepted

$$\deg_G(v)+ \deg_{G'}(v)=n-1$$

where $\deg_G$ and $\deg_{G'}$ represents the degrees in $G$ respectively the complement of $G$.

In you case, if $G=C_n$ and $G'=C_n$ you get

$$2+2=n-1$$

Thus $n=5$ is the only possible one.

To complete the proof you need to check that $C_5$ is isomorphic to its complement, which is easy to do.

P.S. For similar problems, we typically look at edges, but if the graph is of a nice type, degrees are better.

$C_n$ has $n$ edges, it's complement must also have $n$ edges, thus in total they have $2n$ edges. But in total they have $\frac{n(n-1)}{2}$ edges because that's how many $K_n$ has.

share|improve this answer
    
I'm sorry, first of all, thank you for your answer, but could you explain me that how could a $C_{5}$ be isomorphic to its complement? I mean, how can $f(1)$ be connected with $f(2)$ and $f(3)$ and so on? –  Wanderer Dec 3 '13 at 20:49
    
Draw $C_5$. Pick a new color. Draw with this new color the edges not in $C_5$ (which are in fact the diagonals of the pentagon). That is your complement. And what you have there is another pentagon, drawn as a star pentagon. –  N. S. Dec 3 '13 at 20:51
1  
@Wanderer If $C_5$ is the graph $1-2-3-4-5-1$ then its complement is $1-3-5-2-4-1$. So $f(1)=1, f(2)=3, f(3)=5, f(4)=2, f(5)=5$ is your isomorphism. [Completelly irrelevant, but this function is exactly $f(x)=2x-1 \pmod{5}$.] –  N. S. Dec 3 '13 at 20:52
    
helpful and perfect answer. thank you! –  Wanderer Dec 3 '13 at 20:59
    
oh, one more thing. where do we get the initial formula from? (the one with the degrees) –  Wanderer Dec 3 '13 at 21:02
add comment

Your Answer

 
discard

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.