Isomorphism of complements

Task number: 3597

Show that two graphs are isomorphic if and only if their complements are isomorphic.

  • Solution

    Because an isomorphism preserves edges and non-edges in the original graphs, it must also preserve non-edges in the complements (thanks to preserving edges) and edges in the complements (thanks to preserving non-edges).

Difficulty level: Easy task (using definitions and simple reasoning)
Proving or derivation task
Cs translation
Send comment on task by email