5
votes
3answers
397 views

Relationship between triangle free graphs and their minimum degree

Let $T$ be a triangle-free graph on $n$ vertices with minimum degree $\delta$ (which can be $0$). How does one show that $n >2\delta -1$? It seems to be true for bipartite graphs, but I cannot see ...
10
votes
1answer
585 views

A generalization of the triangle counting problem for simple weighted graphs

One nice identity is $$tr(A^3)/6$$ which counts the number of triangles of a graph represented with adjacency matrix $A.$ It also implies that triangle counting can be performed in subcubic time. ...
9
votes
1answer
859 views

4-regular graphs with every edge in a triangle

I am interested in regular graphs in which every edge lies in a triangle. For 3-regular graphs, only the complete graph $K_4$ has this property, so there's not much to see here. For 4-regular ...