We say a graph is triangle-free if there are no three vertices $a,b,c$ such that $a\text{—}b$, $b\text{—}c$, and $c\text{—}a$ are all edges of the graph.
What is the maximum number of edges in a triangle-free graph on 5 vertices?
I have found that a triangle free graph on $5$ vertices is bipartite unless it contains a $5$ cycle. But if it has a $5$ cycle and is triangle free it is a cycle. So I technically want to find the bipartite graph with five vertices with the most edges. However, I am stuck on how to do this. Any hint or the solution would be appreciated.
Best Answer
Solved it!
Let G be a triangle-free graph on 5 vertices, and let E be the number of edges in G.
For every set of three distinct vertices $\{a,b,c\}$, count the number of edges connecting pairs of $a,b,c$. This number is at most 2 for each choice of $\{a,b,c\}$, since G is triangle-free. Thus, if we add this number over all choices of $\{a,b,c\}$, we get at most $\binom 53\cdot 2 = 20$. The sum obtained in this way is 3E, because every edge $a\text{---}b$ is counted as part of three triples. Therefore, $3E\le 20$, which sets an upper bound of $E=6$.
We can realize $E=6$ in the following triangle-free graph:
Notice that all edges extend from a vertex in the left column to a vertex in the right column. This gives clear proof that the graph is triangle-free, since any cycle must be of even length.
We have proved that $E\le 6$ and that we can achieve $E=6$. Therefore, the maximum achievable value of E is exactly $\boxed 6$.