1
$\begingroup$

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^+{}$.

$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 23, 2019 at 1:25
  • $\begingroup$ 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. $\endgroup$ Feb 23, 2019 at 1:50
  • $\begingroup$ 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? $\endgroup$ Feb 23, 2019 at 2:08
  • $\begingroup$ 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. $\endgroup$ Feb 23, 2019 at 2:10
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 23, 2019 at 2:18

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 23, 2019 at 2:34
  • $\begingroup$ 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. $\endgroup$ Feb 23, 2019 at 2:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .