Prove that the size of a graph is at most $16$

Question

Suppose $G$ has order $7$ and $\chi(G) = 3$. Prove that the size of $G$ is at most $16$.

I am really not so sure how to do this problem. This is from a book which teaches some extremal graph theory, combinatorics, and basic ramsey theory. I'm familiar with theorems like Turan's Theorem as well as many other results. But none of them seem to work for this problem.

I don't know if I'm just missing something that seems easy or not.

I tried to utilize Pigeonhole somehow which says that one of the three colors must appear $3$ times. But I got nowhere.

Answer 1

Say $a,b,c$ vertices are of each color. So $a+b+c = 7$ and we have at most $$e\leq ab+ac+bc$$ edges. We have $$49=(a+b+c)^2\geq 3(ab+bc+ca)\geq 3e\implies e\leq 16$$

Answer 2

A simple graph with 7 vertices has at most 21 edges. We distinguish two cases:

1. $G$ is triangle-free. Then it is not hard to show that $G$ has at most 16 edges.

2. $G$ has a triangle $T$. As $G$ is 3-colorable, $G$ does not contain a $K_4$ subgraph. Thus for each vertex $v$ in the complement of $T$, there is an edge between $v$ and $T$ that is not in $G$. Finally, in the complement of $T$ one edge must be missing. Hence at least 5 edges must be missing, as required.