Symmetric and asymmetric graphs

54 Views Asked by At

Let $\Gamma = (V, E)$ be a self-complementary graph with $|V| \geq 2$, how do i prove that exists $\sigma \in S_{V}$ such that:

I. $xy \in E$ if and only if $\sigma(x)\sigma(y) \notin E$.

II. $\sigma^{2} \in$ Aut $\Gamma$, but $\sigma^{2} \neq 1$.

III. The orbits of $\sigma$ induce self-complementary subgraphs of $\Gamma$.

I know some basic results about self-complementary graphs, such as, their order is congruent to $1$ or $0$ mod $4$, any self-complementary graph is connected, the group of automorphisms of a graph is the same as that of its complement.