Skip to main content
fixed construction & added explanation
Source Link
user49822
  • 2.2k
  • 1
  • 13
  • 19

Note that if $G$ be a self-complementary graph with $n$ vertices, then the following gives a self-complementary graph $H$ on $n+4$ vertices: Let $H$ be the graph obtained by adding 4 new vertices $\{a,b,c,d\}$ to $G$, with edges $(a,b),(b,c),(c,d), (a,x), (d, x)$ for any vertex $x$ of $G$.

Why $H$ is self-complementary? As $G$ is self-complementary, there is a permutation $f:V(G)\to V(G)$ such that, for any $u,v$ distinct vertices of $G$, $(u,v)$ is an edge in $G$ if and only if $(f(u),f(v))$ is not an edge in $G$. We can define $g:V(H) \to V(H)$ by $g(a)=b; g(b)=d; g(c)=a; g(d)=c$ and $\left. g\right|_{V(G)} = f$, and it is easy to see that $g$ is an isomorphism between $H$ and its complement.

As there are self-complementary graphs on $1$ vertex and on $4$ vertices, it follows that, for any $n=0,1\quad (mod 4)$ there is a self-complementary graph on $n$ vertices.

Note that if $G$ be a self-complementary graph with $n$ vertices, then the following gives a self-complementary graph $H$ on $n+4$ vertices: Let $H$ be the graph obtained by adding 4 new vertices $\{a,b,c,d\}$ to $G$, with edges $(a,b),(b,c),(c,d), (a,x), (d, x)$ for any vertex $x$ of $G$.

As there are self-complementary graphs on $1$ vertex and on $4$ vertices, it follows that, for any $n=0,1\quad (mod 4)$ there is a self-complementary graph on $n$ vertices.

Note that if $G$ be a self-complementary graph with $n$ vertices, then the following gives a self-complementary graph $H$ on $n+4$ vertices: Let $H$ be the graph obtained by adding 4 new vertices $\{a,b,c,d\}$ to $G$, with edges $(a,b),(b,c),(c,d), (a,x), (d, x)$ for any vertex $x$ of $G$.

Why $H$ is self-complementary? As $G$ is self-complementary, there is a permutation $f:V(G)\to V(G)$ such that, for any $u,v$ distinct vertices of $G$, $(u,v)$ is an edge in $G$ if and only if $(f(u),f(v))$ is not an edge in $G$. We can define $g:V(H) \to V(H)$ by $g(a)=b; g(b)=d; g(c)=a; g(d)=c$ and $\left. g\right|_{V(G)} = f$, and it is easy to see that $g$ is an isomorphism between $H$ and its complement.

As there are self-complementary graphs on $1$ vertex and on $4$ vertices, it follows that, for any $n=0,1\quad (mod 4)$ there is a self-complementary graph on $n$ vertices.

fixed construction
Source Link
user49822
  • 2.2k
  • 1
  • 13
  • 19

Note that if $G$ be a self-complementary graph with $n$ vertices, then the following gives a self-complementary graph $H$ on $n+4$ vertices: Let $H$ be the graph obtained by adding 4 new vertices $\{a,b,c,d\}$ to $G$, with edges $(a,b),(b,c),(c,d), (a,x), (b, x)$$(a,b),(b,c),(c,d), (a,x), (d, x)$ for any vertex $x$ of $G$.

As there are self-complementary graphs on $1$ vertex and on $4$ vertices, it follows that, for any $n=0,1\quad (mod 4)$ there is a self-complementary graph on $n$ vertices.

Note that if $G$ be a self-complementary graph with $n$ vertices, then the following gives a self-complementary graph $H$ on $n+4$ vertices: Let $H$ be the graph obtained by adding 4 new vertices $\{a,b,c,d\}$ to $G$, with edges $(a,b),(b,c),(c,d), (a,x), (b, x)$ for any vertex $x$ of $G$.

As there are self-complementary graphs on $1$ vertex and on $4$ vertices, it follows that, for any $n=0,1\quad (mod 4)$ there is a self-complementary graph on $n$ vertices.

Note that if $G$ be a self-complementary graph with $n$ vertices, then the following gives a self-complementary graph $H$ on $n+4$ vertices: Let $H$ be the graph obtained by adding 4 new vertices $\{a,b,c,d\}$ to $G$, with edges $(a,b),(b,c),(c,d), (a,x), (d, x)$ for any vertex $x$ of $G$.

As there are self-complementary graphs on $1$ vertex and on $4$ vertices, it follows that, for any $n=0,1\quad (mod 4)$ there is a self-complementary graph on $n$ vertices.

Source Link
user49822
  • 2.2k
  • 1
  • 13
  • 19

Note that if $G$ be a self-complementary graph with $n$ vertices, then the following gives a self-complementary graph $H$ on $n+4$ vertices: Let $H$ be the graph obtained by adding 4 new vertices $\{a,b,c,d\}$ to $G$, with edges $(a,b),(b,c),(c,d), (a,x), (b, x)$ for any vertex $x$ of $G$.

As there are self-complementary graphs on $1$ vertex and on $4$ vertices, it follows that, for any $n=0,1\quad (mod 4)$ there is a self-complementary graph on $n$ vertices.