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

I can "show" that the two graphs are in fact self-complementary by making a drawing. How do I "prove" this? How can I rigorously put in words that the complement of P4 is P4 itself?

In other words, how is an isomorphism of a graph proven? Is it possible to do this with a degree sequence? (Does a degree sequence uniquely determine a graph?)

share|cite|improve this question
In this case a good drawing is perfectly rigorous. – Chris Godsil Jun 5 '13 at 11:50
up vote 1 down vote accepted

No, a degree sequence does not determine the graph uniquely (consider two copies of $K_3$ vs. $C_6$).

In order to prove the self-complementarity explicitly, you only need to provide an isomorphism between the graphs -- a bijective mapping between their vertices such that the vertices in original graph are adjacent if and only if their images are adjacent in the other graph. In case of $C_5$ (say, the vertices are named $0,1,2,3,4$ and they're connected in this order), one such isomorphism could be $f(i)=3i+2$.

share|cite|improve this answer

If you want to be more precise, you can give the permutation of vertices which complement the egde relation. This way the reader can easily check that the graph is isomorphic to its complement.

For $P_4$ for instance, if you start with $1- 2-3-4$, it would be $\pi=(3, 1, 4, 2)$, where the $i^{th}$ coordinate is the image of the $i^{th}$ vertex.

For a finite graph, you don't need elaborate tool to prove that your permutation indeed reverses the edge relation $E$: you can just write the exhaustive list showing that for all $i\neq j$, you have $$(i,j)\in E \Leftrightarrow (\pi(i),\pi(j))\notin E$$

share|cite|improve this answer
Can you explain a little more? After I make the permutation, how should I connect the edges for the new vertices? What I understood from your answer is that 1-2-3-4 becomes 2-1-4-3. But then the edge 1-2 is in both graphs. – user81055 Jun 5 '13 at 11:12
It was a typo, I corrected it. – Denis Jun 5 '13 at 11:44

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.