# Number of Vertices in a Self-Complementary Graph

Hello I'm hoping to understand where I went wrong in the below proof. This was given on a quiz and I received 5/40 points for it. My professor said I just gave examples and that I didn't actually give a proof. Any thoughts or comments that help me understand my error in thinking would be greatly appreciated.

$$\textbf{Problem}$$ Suppose $$G$$ is a simple undirected graph with $$n$$ vertices. If $$G$$ is self-complementary, prove that either $$n = 4t$$ or $$n=4t+1$$ for some $$t\in Z^{+}$$. To receive credit for this problem you must write complete sentences, show all of your work, explain all of your reasoning, and include all details. $$\textbf{Proof}$$ Assume BWOC that $$G$$ is self-complementary and that $$n$$ is neither of the form $$4t$$ or $$4t+1$$ for any $$t\in Z^{+}$$. Then $$n$$ can only be one of the following cases:
Case 1: $$n=2$$. If $$n=2$$ then the complete graph on $$G$$ would have $$\frac{2(2-1)}{2}=1$$ edge and thus $$G$$ cannot be self-complementary because $$G$$ must have an even number of edges to be self-complementary.
Case 2: $$n=3$$. If $$n=3$$ then the complete graph on $$G$$ would have $$\frac{3(3-1)}{2}=3$$ edges and thus $$G$$ cannot be self-complementary because G must have an even number of edges to be self=complementary.
Case 3: $$n=4t+2$$ for any $$t\in Z^{+}$$. If $$n=4t+2$$ for any $$t\in Z^{+}$$ then the complete graph on $$G$$ would have $$\frac{(4t+2)(4t+2-1)}{2}=\frac{16t^{2}+12t+2}{2}=8t^{2}+6t+1$$ number of edges and since $$8t^{2}+6t$$ is even the total number of edges on $$G$$ must be odd and thus $$G$$ cannot be self=complementary because $$G$$ must have an even number of edges to be self-complementary.
Case 4: $$n=4t+3$$ for any $$t\in Z^{+}$$. If $$n=4t+3$$ for any $$t\in Z^{+}$$ then the complete graph on $$G$$ would have $$\frac{(4t+3)(4t+3-1)}{2}=\frac{16t^{2}+20t+6}{2}=8t^{2}+10t+2+1$$ number of edges and since $$8t^{2}+10t+2$$ is even the total number of edges on $$G$$ must be odd and thus $$G$$ cannot be self=complementary because $$G$$ must have an even number of edges to be self-complementary.

Thus we have arrived at a contradition. We assumed that $$n$$ is neither of the form $$4t$$ or $$4t+1$$ for any $$t\in Z^{+}$$ and yet $$G$$ is self-complementary and have proved that this is not possible. Thus if a graph $$G$$ with $$n$$ vertices is self-complementary n must either be of the form $$4t$$ or $$4t+1$$ for some $$t\in Z^+{}$$.

• Hmm this is why I am asking for a flaw in my logic. My understanding was that for a graph to be self-complementary it must have exactly half the number of edges of its complete graph. Since it and its complement must have a positive integer value of edges that necessitates that its complete graph must have an even number of edges. Feb 23, 2019 at 1:25
• There I have edited it. I am sorry about my mistake I'm really just trying to understand the problem with my proof. I apologize. Feb 23, 2019 at 1:50
• I understand my wording was poor. You are correct G in this case meant the complete graph on n vertices. I am aware I wrote it very poorly and that was my mistake. My question is, assuming that I stated that the complete graph has an even number of edges to be self-complementary(we were given this information and I should definitely have restated it on the page) and given that I had changed the wording to If a graph on n vertices is self-complementary then the complete graph on n vertices must have an even number of edges" then what logic problems does my proof have? Feb 23, 2019 at 2:08
• I think I misunderstood. The phrase "complete graph on $G$" does not mean anything, but I think you are using it to mean "complete graph on $n$ vertices". You are correct that $n$ cannot be of the form $4t + 2$ or $4t + 3$ because the complete graph would then have an odd number of edges. I suspect your grader had some difficulty following the argument and gave it a lower grade than perhaps it derserved. Feb 23, 2019 at 2:10
• Thank you for the correction. I have been using that vocabulary on the last two homework and I will make sure not to do that again. It makes sense why "Complete graph on G" has no meaning. I don't know how I got that stuck in my head. Feb 23, 2019 at 2:18

The core of your proof is correct, but it's very difficult to read. My primary complaint would be the unnecessary use of contradiction. I might proceed directly as follows:

Let $$G$$ be a self-complementary graph. First note that the number of edges in $$G$$ must be exactly $$\frac{1}{2}\binom{n}{2}$$ since there are a total of $$\binom{n}{2}$$ possible edges on $$n$$ vertices. It follows that $$\binom{n}{2}$$ must be even. Observe the following cases:

• If $$n = 2$$, then $$\binom{n}{2} = 1$$.
• If $$n = 3$$, then $$\binom{n}{2} = 3$$.
• If $$n = 4t + 2$$ for $$t \in \mathbb{Z}^+$$, then $$\binom{n}{2} = 8t^2 + 6t + 1$$.
• If $$n = 4t + 3$$ for $$t \in \mathbb{Z}^+$$, then $$\binom{n}{2} = 8t^2 + 10t + 3$$.

In all these cases, we find that $$\binom{n}{2}$$ is odd. This shows that $$n$$ must be of the form $$4t$$ or $$4t+1$$ for $$t \in \mathbb{Z}^+$$, as desired.

• This is exactly what I was looking for. Using this is much cleaner than what I wrote down and is easy to understand. I will try to use this type of direct argument in the future. Feb 23, 2019 at 2:34
• In most cases, if the contradiction you derive negates your one and only hypothesis (e.g., "$G$ is self-complementary"), then there is probably a clearer direct proof to be had. Best of luck in your studies. Feb 23, 2019 at 2:38