1
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

$$\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.

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – Wanderer
    Dec 3, 2013 at 20:49
  • $\begingroup$ 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. $\endgroup$
    – N. S.
    Dec 3, 2013 at 20:51
  • 1
    $\begingroup$ @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}$.] $\endgroup$
    – N. S.
    Dec 3, 2013 at 20:52
  • $\begingroup$ helpful and perfect answer. thank you! $\endgroup$
    – Wanderer
    Dec 3, 2013 at 20:59
  • $\begingroup$ oh, one more thing. where do we get the initial formula from? (the one with the degrees) $\endgroup$
    – Wanderer
    Dec 3, 2013 at 21:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .