Maximum number of edges in a graph satisfying conditions

Question

Problem:

There is a graph with 40 vertices. It is known that any edge has at least one endpoint, on which no more than four other edges are incident. What is the maximum number of edges that this graph can have? No multiple edges or loops are allowed.

My thoughts so far:

We consider this graph to be bipartite, with one half consisting of all vertices of degree five, and the second half – remaining vertices. The reason this is valid is that if the second half has at least 5 vertices, we can connect those to all the vertices in the first half, thus meeting the bipartite requirements. In this case, the maximum number of edges is achieved when there are exactly 5 vertices in the second half: $35 \times 5=175$.

On the other hand, if the second half has less than 5 vertices, then the total number of edges is obviously smaller.

Answer 1

For a vertex $v$ with $a$ neighbours of degree $\leq 5$ and $b$ neihgbours of degree $> 5$ we define $f(v)$ as $a/2+b$.

Notice $m = \sum\limits_{v | d(v) \leq 5}^n f(v)$.

Let $k$ be the number of vertices of degree $\leq 5$.

If $k\leq 35$ then clearly $m \leq 35\cdot 5=175$.

If $k=35+l$ with $k\in \{1,\dots,5\}$ then each summand is at most $5-\frac{l}{2}$ so $\sum\limits_{v | d(v) \leq 5}^n f(v) \leq (35+l)(5-\frac{l}{2}) <175$.