Triangle-free graph with 5 vertices

Question

What is the maximum number of edges in a triangle-free graph on 5 vertices?

No answers, please...just hints.

I believe that E $\leq$ 5, but I'm not sure where to go from there.

Answer 1

Hint: 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.

Hence you want to find the bipartite graph with five vertices with the most edges.

Answer 2

It is not true that this is $5$. Connect one point to three points, and connect the remaining point to the same three points.

To proof this optimal you could start distinguishing cases by maximum degree of a vertex. There might be a more elegant argument yet I would not know it momentarily.

Answer 3

Consider a pentagon. If you try to add any more edges to the pentagon a triangle will be formed. Thus for graph having a cycle containing 5 vertices ( all vertices that is ) can have at maximum 5 edges without violating the condition. Now consider bi-partite graphs with a total of 5 vertices , say $x$ in one group and $5-x$ in other. Bipartite graphs can't have odd length cycles. Thus no triangles and no pentagons. As we have already taken care of pentagons. You just need to find maximum in case of bi-partite graph. In bi-partite graph maximum edges can be $(5-x)*x$. Hope I have not answered completely.

Answer 4

Going off the bipartite graph hint, you can also look at the eigenvalues of the adjacency matrix. Note that $tr(A) = \sum_{i} \lambda_{i}$, where $A$ is the adjacency matrix and $\lambda_{i}$ are the eigenvalues. Note $tr(A)$ is the trace of $A$, which is the sum of the diagonal entries.

So: $\sum_{i=1}^{5} \lambda_{i} = 0$.

We also have:
$\sum_{i=1}^{5} \lambda_{i}^{2} = tr(A^{2}) = 2E$ (The Handshake Lemma)
$\sum_{i=1}^{5} \lambda_{i}^{3} = tr(A^{3}) = 6C_{3}$

So if we square the adjacency matrix, the diagonal elements are the edges incident to each vertex. And cubing the adjacency matrix leaves us with the diagonal elements counting triangles each vertex is a part of. We divide out by $S_{3}$ to account for any ordering of the vertices of the triangle on a walk.

Now we also have another fact: $\lambda_{i} = -\lambda_{n-i}$ iff $G$ is bipartite. So $\lambda_{1} = -\lambda_{5}$ and $\lambda_{2} = -\lambda_{4}$. That gives us $\lambda_{3} = 0$.

And so: $2\lambda_{1}^{2} + 2\lambda_{2}^{2} = 2E \implies \lambda_{1}^{2} + \lambda_{2}^{2} = E$.

And a last fact: $d_{avg}(G) \leq \lambda_{1} \leq \Delta(G)$. That is, $\lambda_{1}$ is between the average degree of the graph and the largest vertex degree.

It might be fun to play around with the eigenvalues here to see what you come up with.