1
$\begingroup$

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?

Improve this question
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Misha Lavrov Aug 26 '18 at 21:40
1
$\begingroup$

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$.

Improve this answer
$\endgroup$
  • $\begingroup$ Why does every edge appear $\binom{34}{2}$ times and not $\binom{36}{2}$? $\endgroup$ – Archetype2142 Aug 27 '18 at 7:08
  • 1
    $\begingroup$ Because that edge already has two vertices and to make a subgraph with four vertices we need two other vertices out of the remaining 34. $\endgroup$ – Marco Aug 27 '18 at 10:54

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.