# Calculating number of edges in a graph

The prompt is to find the number of edges of graph with $36$ vertices given that from every $4$ vertices, at least $2$ of them have to have an edge between them. We must prove that the graph G has at least 105 edges or find some non-trivial lower limit on the number of edges.

If we join $2$ vertices of all the $36$ vertices, we are left with $18$ edges, how is this possible, how should I go on about solving a problem like this? I know that $2|E| = deg(v)$ by handshake theorem, how should I find the degree of each vertex here?

• If you divide up the 36 vertices into pairs $\{1,2\}, \{3,4\}, \{5,6\}, \dots$ and connect every pair by an edge, that doesn't accomplish the task in the prompt: the four vertices $\{1,3,5,7\}$ have no edges between them. – Misha Lavrov Aug 26 '18 at 21:40

Consider the set of all subgraphs of $G$ that have four vertices. There are ${36\choose 4}$ such graphs. For each such subgraph $H$, count the number of edges $e(H)$ in it. Then calculate $\sum_H e(H)$ in two ways. One way is to note that every edge appears ${34 \choose 2}$ many times. So $\sum_H e(H)=e(G) \times {34 \choose 2}$. On the other hand, each subgraph $H$ has at least one edge, so $\sum_H e(H) \geq {36 \choose 4}$. In other words,
$$e(G) \times {34 \choose 2} \geq {36 \choose 4}.$$
Simplifying both sides gives $e(G) \geq 105$.
• Why does every edge appear $\binom{34}{2}$ times and not $\binom{36}{2}$? – Archetype2142 Aug 27 '18 at 7:08