0
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ In this case a good drawing is perfectly rigorous. $\endgroup$ Jun 5 '13 at 11:50
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – user81055
    Jun 5 '13 at 11:12
  • $\begingroup$ It was a typo, I corrected it. $\endgroup$
    – Denis
    Jun 5 '13 at 11:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.