# Prove path P4 and the cycle C5 are self-complementary

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?)

• In this case a good drawing is perfectly rigorous. Jun 5 '13 at 11:50

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