Mixing
How many vertices can a self-complementary graph have?
Clash Royale CLAN TAG#URR8PPP
up vote
4
down vote
favorite
Counting edges easily shows that if $n$ is congruent to 2 or 3 modulo 4, there is no self-complementary graph on $n$ vertices. Is the converse true?
What I know: Paley graphs are self-complementary, so if $n$ is congruent to 1 mod 4 and is a prime power, then there is a self-complementary graph on $n$ vertices. Also, the set of $n$ such that there is a self-complementary graph on $n$ vertices is closed under products. Together (since there is a self-complementary graph on 4 vertices) these imply that if the prime factorization of $n$ has even number of 2s and an even number of every prime congruent to 3 modulo 4 then there is a self-complementary graph on $n$ vertices.
graph-theory
edited Aug 31 at 20:59
bof
4,4801930
asked Aug 31 at 19:16
Aaron Hill
584
add a comment |Â
up vote
4
down vote
favorite
Counting edges easily shows that if $n$ is congruent to 2 or 3 modulo 4, there is no self-complementary graph on $n$ vertices. Is the converse true?
What I know: Paley graphs are self-complementary, so if $n$ is congruent to 1 mod 4 and is a prime power, then there is a self-complementary graph on $n$ vertices. Also, the set of $n$ such that there is a self-complementary graph on $n$ vertices is closed under products. Together (since there is a self-complementary graph on 4 vertices) these imply that if the prime factorization of $n$ has even number of 2s and an even number of every prime congruent to 3 modulo 4 then there is a self-complementary graph on $n$ vertices.
graph-theory
edited Aug 31 at 20:59
bof
4,4801930
asked Aug 31 at 19:16
Aaron Hill
584
This follows from formulas (4) and (5) of this paper: doi.org/10.1112/jlms/s1-38.1.99
– Ian Agol
Aug 31 at 20:10
3
This is a standard exercise in graph theory textbooks.
– bof
Aug 31 at 20:59
add a comment |Â
up vote
4
down vote
favorite
up vote
4
down vote
favorite
Counting edges easily shows that if $n$ is congruent to 2 or 3 modulo 4, there is no self-complementary graph on $n$ vertices. Is the converse true?
What I know: Paley graphs are self-complementary, so if $n$ is congruent to 1 mod 4 and is a prime power, then there is a self-complementary graph on $n$ vertices. Also, the set of $n$ such that there is a self-complementary graph on $n$ vertices is closed under products. Together (since there is a self-complementary graph on 4 vertices) these imply that if the prime factorization of $n$ has even number of 2s and an even number of every prime congruent to 3 modulo 4 then there is a self-complementary graph on $n$ vertices.
graph-theory
edited Aug 31 at 20:59
bof
4,4801930
asked Aug 31 at 19:16
Aaron Hill
584
Counting edges easily shows that if $n$ is congruent to 2 or 3 modulo 4, there is no self-complementary graph on $n$ vertices. Is the converse true?
What I know: Paley graphs are self-complementary, so if $n$ is congruent to 1 mod 4 and is a prime power, then there is a self-complementary graph on $n$ vertices. Also, the set of $n$ such that there is a self-complementary graph on $n$ vertices is closed under products. Together (since there is a self-complementary graph on 4 vertices) these imply that if the prime factorization of $n$ has even number of 2s and an even number of every prime congruent to 3 modulo 4 then there is a self-complementary graph on $n$ vertices.
graph-theory
edited Aug 31 at 20:59
bof
4,4801930
asked Aug 31 at 19:16
Aaron Hill
584
edited Aug 31 at 20:59
bof
4,4801930
edited Aug 31 at 20:59
bof
4,4801930
edited Aug 31 at 20:59
bof
4,4801930
4,4801930
asked Aug 31 at 19:16
Aaron Hill
584
asked Aug 31 at 19:16
Aaron Hill
584
asked Aug 31 at 19:16
Aaron Hill
584
584
This follows from formulas (4) and (5) of this paper: doi.org/10.1112/jlms/s1-38.1.99
– Ian Agol
Aug 31 at 20:10
3
This is a standard exercise in graph theory textbooks.
– bof
Aug 31 at 20:59
add a comment |Â
This follows from formulas (4) and (5) of this paper: doi.org/10.1112/jlms/s1-38.1.99
– Ian Agol
Aug 31 at 20:10
3
This is a standard exercise in graph theory textbooks.
– bof
Aug 31 at 20:59
This follows from formulas (4) and (5) of this paper: doi.org/10.1112/jlms/s1-38.1.99
– Ian Agol
Aug 31 at 20:10
This follows from formulas (4) and (5) of this paper: doi.org/10.1112/jlms/s1-38.1.99
– Ian Agol
Aug 31 at 20:10
3
3
This is a standard exercise in graph theory textbooks.
– bof
Aug 31 at 20:59
This is a standard exercise in graph theory textbooks.
– bof
Aug 31 at 20:59
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
7
down vote
accepted
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. gright|_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,1quad (mod 4)$ there is a self-complementary graph on $n$ vertices.
answered Aug 31 at 20:11
user49822
57138
Nice construction. It works for 0 points, but not for 1 point. Perhaps cx and not bx? Gerhard "Hasn't Checked On Larger Graphs" Paseman, 2018.08.31.
– Gerhard Paseman
Aug 31 at 20:40
@GerhardPaseman fixed, and added explanation
– user49822
Aug 31 at 20:58
add a comment |Â
up vote
4
down vote
Quoting an answer I posted some time ago on MathSE:
Take a complete graph with vertex set $V$ and edge set $E=Vchoose2$. Let $alpha$ be any permutation of $V$ in which the length of each cycle is a multiple of $4$, except for at most one $1$-cycle. Of course, such permutations exist if and only if $|V|equiv 0$ or $1pmod 4$. (N.B. The word "cycle" is used here in its group theory sense, not its graph theory sense!)
Let $beta$ be the permutation of $E$ induced by $alpha$. Observe that $beta$ contains only cycles of even length. Color the edges in each cycle alternately black and white. The graph consisting of the black edges is self-complementary; the permutation $alpha$ is an isomorphism between the black graph and the white graph.
Example. To construct self-complementary graphs of order $5$, take $V=a,b,c,d,e$ and let $alpha=(a;b;c;d)(e)$ so that $beta=(ab;bc;cd;ad)(ac;bd)(ae;be;ce;de);$. If we choose the edges $ab,cd$ and $ac$ (i.e. "color them black") we get a $4$-point path $P_4$. Now we can choose the edges $be,de$ obtaining the self-complementary graph $C_5$, or else we can choose $ae,ce$ obtaining the other self-complementary graph of order $5$, the bull graph.
An alternative proof is often given in graph theory textbooks, e.g., quoting Exercise 1.1.31 on p. 17 of Douglas B. West's Introduction to Graph Theory, second edition:
Prove that a self-complementary graph with $n$ vertices exists if and only if $n$ or $n-1$ is divisible by $4.$ (Hint: When $n$ is divisible by $4,$ generalize the structure of $P_4$ by splitting the vertices into four groups. For $nequiv1$ mod $4,$ add one vertex to the graph constructed for $n-1.$)
answered Aug 31 at 21:20
bof
4,4801930
Do all such finite complementary graphs arise this way? Gerhard "Not Fishing For More Complements" Paseman, 2018.08.31.
– Gerhard Paseman
Aug 31 at 21:40
@GerhardPaseman Yes, of course. If $G=(V,E)$ is a self-complementary graph, let $alphainoperatornameSym(V)$ be an anti-automorphism of $G.$
– bof
Aug 31 at 21:59
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
7
down vote
accepted
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. gright|_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,1quad (mod 4)$ there is a self-complementary graph on $n$ vertices.
answered Aug 31 at 20:11
user49822
57138
Nice construction. It works for 0 points, but not for 1 point. Perhaps cx and not bx? Gerhard "Hasn't Checked On Larger Graphs" Paseman, 2018.08.31.
– Gerhard Paseman
Aug 31 at 20:40
@GerhardPaseman fixed, and added explanation
– user49822
Aug 31 at 20:58
add a comment |Â
up vote
7
down vote
accepted
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. gright|_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,1quad (mod 4)$ there is a self-complementary graph on $n$ vertices.
answered Aug 31 at 20:11
user49822
57138
Nice construction. It works for 0 points, but not for 1 point. Perhaps cx and not bx? Gerhard "Hasn't Checked On Larger Graphs" Paseman, 2018.08.31.
– Gerhard Paseman
Aug 31 at 20:40
@GerhardPaseman fixed, and added explanation
– user49822
Aug 31 at 20:58
add a comment |Â
up vote
7
down vote
accepted
up vote
7
down vote
accepted
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. gright|_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,1quad (mod 4)$ there is a self-complementary graph on $n$ vertices.
answered Aug 31 at 20:11
user49822
57138
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. gright|_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,1quad (mod 4)$ there is a self-complementary graph on $n$ vertices.
answered Aug 31 at 20:11
user49822
57138
edited Aug 31 at 20:57
answered Aug 31 at 20:11
user49822
57138
answered Aug 31 at 20:11
user49822
57138
answered Aug 31 at 20:11
user49822
57138
57138
Nice construction. It works for 0 points, but not for 1 point. Perhaps cx and not bx? Gerhard "Hasn't Checked On Larger Graphs" Paseman, 2018.08.31.
– Gerhard Paseman
Aug 31 at 20:40
@GerhardPaseman fixed, and added explanation
– user49822
Aug 31 at 20:58
add a comment |Â
Nice construction. It works for 0 points, but not for 1 point. Perhaps cx and not bx? Gerhard "Hasn't Checked On Larger Graphs" Paseman, 2018.08.31.
– Gerhard Paseman
Aug 31 at 20:40
@GerhardPaseman fixed, and added explanation
– user49822
Aug 31 at 20:58
Nice construction. It works for 0 points, but not for 1 point. Perhaps cx and not bx? Gerhard "Hasn't Checked On Larger Graphs" Paseman, 2018.08.31.
– Gerhard Paseman
Aug 31 at 20:40
Nice construction. It works for 0 points, but not for 1 point. Perhaps cx and not bx? Gerhard "Hasn't Checked On Larger Graphs" Paseman, 2018.08.31.
– Gerhard Paseman
Aug 31 at 20:40
@GerhardPaseman fixed, and added explanation
– user49822
Aug 31 at 20:58
@GerhardPaseman fixed, and added explanation
– user49822
Aug 31 at 20:58
add a comment |Â
up vote
4
down vote
Quoting an answer I posted some time ago on MathSE:
Take a complete graph with vertex set $V$ and edge set $E=Vchoose2$. Let $alpha$ be any permutation of $V$ in which the length of each cycle is a multiple of $4$, except for at most one $1$-cycle. Of course, such permutations exist if and only if $|V|equiv 0$ or $1pmod 4$. (N.B. The word "cycle" is used here in its group theory sense, not its graph theory sense!)
Let $beta$ be the permutation of $E$ induced by $alpha$. Observe that $beta$ contains only cycles of even length. Color the edges in each cycle alternately black and white. The graph consisting of the black edges is self-complementary; the permutation $alpha$ is an isomorphism between the black graph and the white graph.
Example. To construct self-complementary graphs of order $5$, take $V=a,b,c,d,e$ and let $alpha=(a;b;c;d)(e)$ so that $beta=(ab;bc;cd;ad)(ac;bd)(ae;be;ce;de);$. If we choose the edges $ab,cd$ and $ac$ (i.e. "color them black") we get a $4$-point path $P_4$. Now we can choose the edges $be,de$ obtaining the self-complementary graph $C_5$, or else we can choose $ae,ce$ obtaining the other self-complementary graph of order $5$, the bull graph.
An alternative proof is often given in graph theory textbooks, e.g., quoting Exercise 1.1.31 on p. 17 of Douglas B. West's Introduction to Graph Theory, second edition:
Prove that a self-complementary graph with $n$ vertices exists if and only if $n$ or $n-1$ is divisible by $4.$ (Hint: When $n$ is divisible by $4,$ generalize the structure of $P_4$ by splitting the vertices into four groups. For $nequiv1$ mod $4,$ add one vertex to the graph constructed for $n-1.$)
answered Aug 31 at 21:20
bof
4,4801930
Do all such finite complementary graphs arise this way? Gerhard "Not Fishing For More Complements" Paseman, 2018.08.31.
– Gerhard Paseman
Aug 31 at 21:40
@GerhardPaseman Yes, of course. If $G=(V,E)$ is a self-complementary graph, let $alphainoperatornameSym(V)$ be an anti-automorphism of $G.$
– bof
Aug 31 at 21:59
add a comment |Â
up vote
4
down vote
Quoting an answer I posted some time ago on MathSE:
Take a complete graph with vertex set $V$ and edge set $E=Vchoose2$. Let $alpha$ be any permutation of $V$ in which the length of each cycle is a multiple of $4$, except for at most one $1$-cycle. Of course, such permutations exist if and only if $|V|equiv 0$ or $1pmod 4$. (N.B. The word "cycle" is used here in its group theory sense, not its graph theory sense!)
Let $beta$ be the permutation of $E$ induced by $alpha$. Observe that $beta$ contains only cycles of even length. Color the edges in each cycle alternately black and white. The graph consisting of the black edges is self-complementary; the permutation $alpha$ is an isomorphism between the black graph and the white graph.
Example. To construct self-complementary graphs of order $5$, take $V=a,b,c,d,e$ and let $alpha=(a;b;c;d)(e)$ so that $beta=(ab;bc;cd;ad)(ac;bd)(ae;be;ce;de);$. If we choose the edges $ab,cd$ and $ac$ (i.e. "color them black") we get a $4$-point path $P_4$. Now we can choose the edges $be,de$ obtaining the self-complementary graph $C_5$, or else we can choose $ae,ce$ obtaining the other self-complementary graph of order $5$, the bull graph.
An alternative proof is often given in graph theory textbooks, e.g., quoting Exercise 1.1.31 on p. 17 of Douglas B. West's Introduction to Graph Theory, second edition:
Prove that a self-complementary graph with $n$ vertices exists if and only if $n$ or $n-1$ is divisible by $4.$ (Hint: When $n$ is divisible by $4,$ generalize the structure of $P_4$ by splitting the vertices into four groups. For $nequiv1$ mod $4,$ add one vertex to the graph constructed for $n-1.$)
answered Aug 31 at 21:20
bof
4,4801930
Do all such finite complementary graphs arise this way? Gerhard "Not Fishing For More Complements" Paseman, 2018.08.31.
– Gerhard Paseman
Aug 31 at 21:40
@GerhardPaseman Yes, of course. If $G=(V,E)$ is a self-complementary graph, let $alphainoperatornameSym(V)$ be an anti-automorphism of $G.$
– bof
Aug 31 at 21:59
add a comment |Â
up vote
4
down vote
up vote
4
down vote
Quoting an answer I posted some time ago on MathSE:
Take a complete graph with vertex set $V$ and edge set $E=Vchoose2$. Let $alpha$ be any permutation of $V$ in which the length of each cycle is a multiple of $4$, except for at most one $1$-cycle. Of course, such permutations exist if and only if $|V|equiv 0$ or $1pmod 4$. (N.B. The word "cycle" is used here in its group theory sense, not its graph theory sense!)
Let $beta$ be the permutation of $E$ induced by $alpha$. Observe that $beta$ contains only cycles of even length. Color the edges in each cycle alternately black and white. The graph consisting of the black edges is self-complementary; the permutation $alpha$ is an isomorphism between the black graph and the white graph.
Example. To construct self-complementary graphs of order $5$, take $V=a,b,c,d,e$ and let $alpha=(a;b;c;d)(e)$ so that $beta=(ab;bc;cd;ad)(ac;bd)(ae;be;ce;de);$. If we choose the edges $ab,cd$ and $ac$ (i.e. "color them black") we get a $4$-point path $P_4$. Now we can choose the edges $be,de$ obtaining the self-complementary graph $C_5$, or else we can choose $ae,ce$ obtaining the other self-complementary graph of order $5$, the bull graph.
An alternative proof is often given in graph theory textbooks, e.g., quoting Exercise 1.1.31 on p. 17 of Douglas B. West's Introduction to Graph Theory, second edition:
Prove that a self-complementary graph with $n$ vertices exists if and only if $n$ or $n-1$ is divisible by $4.$ (Hint: When $n$ is divisible by $4,$ generalize the structure of $P_4$ by splitting the vertices into four groups. For $nequiv1$ mod $4,$ add one vertex to the graph constructed for $n-1.$)
answered Aug 31 at 21:20
bof
4,4801930
Quoting an answer I posted some time ago on MathSE:
Take a complete graph with vertex set $V$ and edge set $E=Vchoose2$. Let $alpha$ be any permutation of $V$ in which the length of each cycle is a multiple of $4$, except for at most one $1$-cycle. Of course, such permutations exist if and only if $|V|equiv 0$ or $1pmod 4$. (N.B. The word "cycle" is used here in its group theory sense, not its graph theory sense!)
Let $beta$ be the permutation of $E$ induced by $alpha$. Observe that $beta$ contains only cycles of even length. Color the edges in each cycle alternately black and white. The graph consisting of the black edges is self-complementary; the permutation $alpha$ is an isomorphism between the black graph and the white graph.
Example. To construct self-complementary graphs of order $5$, take $V=a,b,c,d,e$ and let $alpha=(a;b;c;d)(e)$ so that $beta=(ab;bc;cd;ad)(ac;bd)(ae;be;ce;de);$. If we choose the edges $ab,cd$ and $ac$ (i.e. "color them black") we get a $4$-point path $P_4$. Now we can choose the edges $be,de$ obtaining the self-complementary graph $C_5$, or else we can choose $ae,ce$ obtaining the other self-complementary graph of order $5$, the bull graph.
An alternative proof is often given in graph theory textbooks, e.g., quoting Exercise 1.1.31 on p. 17 of Douglas B. West's Introduction to Graph Theory, second edition:
Prove that a self-complementary graph with $n$ vertices exists if and only if $n$ or $n-1$ is divisible by $4.$ (Hint: When $n$ is divisible by $4,$ generalize the structure of $P_4$ by splitting the vertices into four groups. For $nequiv1$ mod $4,$ add one vertex to the graph constructed for $n-1.$)
answered Aug 31 at 21:20
bof
4,4801930
edited Sep 1 at 7:38
answered Aug 31 at 21:20
bof
4,4801930
answered Aug 31 at 21:20
bof
4,4801930
answered Aug 31 at 21:20
bof
4,4801930
4,4801930
Do all such finite complementary graphs arise this way? Gerhard "Not Fishing For More Complements" Paseman, 2018.08.31.
– Gerhard Paseman
Aug 31 at 21:40
@GerhardPaseman Yes, of course. If $G=(V,E)$ is a self-complementary graph, let $alphainoperatornameSym(V)$ be an anti-automorphism of $G.$
– bof
Aug 31 at 21:59
add a comment |Â
Do all such finite complementary graphs arise this way? Gerhard "Not Fishing For More Complements" Paseman, 2018.08.31.
– Gerhard Paseman
Aug 31 at 21:40
@GerhardPaseman Yes, of course. If $G=(V,E)$ is a self-complementary graph, let $alphainoperatornameSym(V)$ be an anti-automorphism of $G.$
– bof
Aug 31 at 21:59
Do all such finite complementary graphs arise this way? Gerhard "Not Fishing For More Complements" Paseman, 2018.08.31.
– Gerhard Paseman
Aug 31 at 21:40
Do all such finite complementary graphs arise this way? Gerhard "Not Fishing For More Complements" Paseman, 2018.08.31.
– Gerhard Paseman
Aug 31 at 21:40
@GerhardPaseman Yes, of course. If $G=(V,E)$ is a self-complementary graph, let $alphainoperatornameSym(V)$ be an anti-automorphism of $G.$
– bof
Aug 31 at 21:59
@GerhardPaseman Yes, of course. If $G=(V,E)$ is a self-complementary graph, let $alphainoperatornameSym(V)$ be an anti-automorphism of $G.$
– bof
Aug 31 at 21:59
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f309555%2fhow-many-vertices-can-a-self-complementary-graph-have%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
This follows from formulas (4) and (5) of this paper: doi.org/10.1112/jlms/s1-38.1.99
– Ian Agol
Aug 31 at 20:10
3
This is a standard exercise in graph theory textbooks.
– bof
Aug 31 at 20:59