I'm not sure how to prove the maximum number of edges. I know that a graph with $6$ vertices should have a max of $6(6-1)/2 = 15$ edges, but I don't know how to prove the max edges with less than two $3$-cycles. I have drawn a few graphs and I get $7$ each time, but how do I prove it? Is $7$ even right? I'm not sure.
[Math] How to prove the maximum number of edges in a graph with $6$ vertices and less then two $3$-cycles
graph theory
Best Answer
Suppose any vertex of the graph has degree $4$ or more. Then there are at least $\binom 42 = 6$ edges connecting its neighbors; including any of those edges would create a triangle. So at least $6$ edges must be missing in this case, and the number of edges in the graph is at most $9$.
On the other hand, suppose all vertices have degree at most $3$. The sum of degrees in a graph is twice the number of edges, by the handshaking lemma, so the number of edges in this case is at most $\frac12(3+3+3+3+3+3) = 9$.
Since one of these must be the case, $9$ is a universal upper bound. As @PJK points out in the comments, in the second case, we can achieve $9$ by making a $3$-regular graph with no triangles:
We can also think of this graph as the complete bipartite graph $K_{3,3}$.
It is not a coincidence that the complete bipartite graph is the graph with the maximum number of edges here: Mantel's theorem says that for $n$ vertices, the maximum number of edges in a triangle-free graph is achieved by the balanced or nearly-balanced complete bipartite graph $K_{\lfloor n/2\rfloor, \lceil n/2 \rceil}$.