What's wrong with this proof that a graph with 6 vertices or its complement contains a subgraph isomorphic to $K_3$?

1k Views Asked by At

Theorem: If a graph $G$ has 6 vertices, then either $G$ or its complement $\overline{G}$ contains a subgraph isomorphic to the complete graph $K_3$.

I understand the proof, related to Ramsey Theory, that utilizes the pigeonhole principle and has already been posted on the site here. I am therefore not looking for a proof, but rather seeking to learn what is wrong with the following proof (or, perhaps, that it is acceptable):

Proof: If $G$ contains a subgraph isomorphic to $K_3$, then we are done.

Otherwise, $G$ must contain 3 vertices - call them $a$, $b$, and $c$ - such that the edges $ab$, $bc$, and $ac$ are not contained within the edge set of $G$. Therefore $\overline{G}$ contains the edges $ab$, $bc$, and $ac$, which form a subgraph isomorphic to $K_3$. QED

It seems to have a valid structure, as we prove the proposition "$P$ or $Q$" by showing "not $P$ implies $Q$." But this proof seems somehow unsatisfying. So where, if anywhere, does it go wrong?

3

There are 3 best solutions below

0
On BEST ANSWER

The problem is that the statement that $G$ doesn't contain all of $ab, bc, ac$ only implies that $\overline G$ contains at least one of $ab, bc, ac$.

0
On

Your otherwise should only be that 'at least one of $ab$, $bc$,$ac$ is contained in the edge set of $\overline G$.

0
On

Did you notice that you do not even use $|G|=6$ in your proof? Hence it seems to prove the claim also for $|G|=5$ - or even for $|G|=3$.