Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
It is known (and not so hard to prove) that any self-complementary graph with more than one vertex has diameter $2$ or $3$.
What would be the simplest example (i.e., with the least number of vertices) of a self-complementary graph of diameter $2$?
Edit: As pointed out in the comments, $C_5$ is the answer to the question. What would be the next self-complementary graph with diameter 2?
For any $n\in\mathbb N,$ here's how you can construct a self-complementary graph of diameter $2$ and order $4n+1.$
Choose a graph $G$ of order $n.$
Start with a $C_5$ graph, with vertices $A,B,C,D,E$ and edges $AB,BC,CD,DE,EA.$
Replace each of the vertices $B$ and $E$ with a copy of $G,$ and replace each of the vertices $C$ and $D$ with a copy of the complementary graph $\overline G.$
More precisely: The graph has vertex set $A\cup B\cup C\cup D\cup E$ where $A,B,C,D,E$ are disjoint sets and $|A|=1$ and $|B|=|C|=|D|=|E|=n.$ The induced subgraphs on $B$ and $E$ are isomorphic to $G,$ the induced subgraphs on $C$ and $D$ are isomorphic to $\overline G.$ There are edges joining all vertices in $A$ to all vertices in $B,$ all vertices in $B$ to all vertices in $C,$ all vertices in $C$ to all vertices in $D,$ all vertices in $D$ to all vertices in $E,$ and all vertices in $E$ to all vertices in $A.$ On the other hand, there are no edges between $A$ and $C,$ or between $C$ and $E,$ or between $E$ and $B,$ or between $B$ and $D,$ or between $D$ and $A.$
In other words: Just use the most obvious construction of a self-complementary graph of order $4n+1.$
Example: For $G=K_2$ it looks like
In my previous answer I showed how to construct self-complementary graphs of diameter $2$ and order $4n+1$ for every $n\in\mathbb N.$ (In a similar way we can construct self-complementary graphs of diameter $3$ and orders $4n$ and $4n+1$ for every $n\in\mathbb N.$) In this answer I sketch a non-constructive proof of the fact that self-complementary graphs of diameter $2$ and order $4n$ exist for all sufficiently large $n.$
Let $K_{4n}=(V,E).$ Partition $V$ into $4$-element sets $V_1,\dots,V_n.$ Choose a permutation $\pi$ of $V$ which permutes each $V_i$ cyclically. Let $\pi'$ be the corresponding permutation of $E,$ which maps an edge $xy$ to the edge $\pi(x)\pi(y).$ We will get a self-complementary graph on the vertex set $V$ by coloring each edge black or white, so that $\pi'$ maps black edges to white edges and vice versa; then $\pi$ is an isomorphism from the black graph to the white graph.
Because of the cycle structure of $\pi,$ all cycles of $\pi'$ have even length, in fact, length $2$ or $4.$ (WARNING: we are using the word "cycle" in the permutation group sense, not the graph theory sense.) Therefore, we can get a self-complementary graph by coloring the edges of each cycle of $\pi'$ alternately black and white.
There are two ways to color each cycle. Let's randomize the process by letting an independent fair coin toss determine the coloring of each cycle. Let $p_n$ be the probability that the resulting self-complementary graph will have diameter greater than $2.$ It is pretty clear that $p_n\to0$ as $n\to\infty;$ my crude estimate is $p_n\le\frac12(\frac34)^{n-2}\binom{4n}2.$ Hence for sufficiently large $n$ we have $p_n\lt1$ which means that are self-complementary graphs of diameter $2.$
