Triangles in a simple graph

Let G be a simple (no loops, no parallel arrows) graph with E edges and V vertices. Then G contains at least \dfrac{E}{3V}(4E-V^2) triangles.

Triangles in a simple graph

One thought on “Triangles in a simple graph

  1. Let us count, first, a lower bound for the number of triangles that contain an edge v,w. Note that this is exactly the number of common neighbours of $late v,w$, which is at least \deg v+\deg w-|G| (by inclusion exclusion on two sets). Let \Delta be the number of triangles in G. Then 3\Delta\geqslant \sum_{w,v\; \rm edge} \deg v+\deg w- EV.

    Now the first sum is \dfrac 1 2 \sum_{v\in V(G)}\sum_{w\in N(v)}(\deg v +\deg w) which equals \dfrac 1 2 \left(\sum_v (\deg v)^ 2 + \sum_{v\in V(G)} \sum_{w\in N(v)} \deg w \right), and this last sum is also \sum_v (\deg v)^ 2. Hence 3\Delta is at least \sum_v (\deg v)^ 2 -EV. But V \sum_v (\deg v)^ 2 \geqslant (2E)^2: the left side counts (v,v',w,w') such that vw,vw' are edges of G, and the right side counts (v,v',w,w') such that vv',ww' are edges of G. The result follows.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s