2
$\begingroup$

Suppose a connected simple graph has m edges and there are at most n vertices and the degree of each vertex is at least k. How many triangles are there in the graph at most? The tighter the bound, the better.

$\endgroup$
1
$\begingroup$

A simple graph can have at most $\binom{n}{2}$ edges, which would make it complete. The spectrum of $K_{n}$ is $(n-1)$, with multiplicity $1$; and $-1$, with multiplicity $n-1$. So $K_{5}$ has eigenvalues $4, -1, -1, -1, -1$. Now the number of triangles in a complete graph is given by $\sum_{i=1}^{n} \lambda_{i}^{3} = (n-1)^{3} - (n-1)$, for $\lambda_{i}$ an eigenvalue of $K_{n}$ (on the adjacency matrix). Each edge you remove from $K_{n}$ removes at most $n-2$ triangles.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.