Let be a simple (no loops, no parallel arrows) graph with edges and vertices. Then contains at least triangles.

Advertisements

Skip to content
# Triangles in a simple graph

##
One thought on “Triangles in a simple graph”

### Leave a Reply

Let be a simple (no loops, no parallel arrows) graph with edges and vertices. Then contains at least triangles.

Advertisements

%d bloggers like this:

Let us count, first, a lower bound for the number of triangles that contain an edge . Note that this is exactly the number of common neighbours of $late v,w$, which is at least (by inclusion exclusion on two sets). Let be the number of triangles in . Then .

Now the first sum is which equals , and this last sum is also . Hence is at least . But : the left side counts such that are edges of , and the right side counts such that are edges of . The result follows.

LikeLike