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