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

Maximum number of edges in a graph satisfying conditions
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.
You can still ask an expert for help

## Want to know more about Discrete math?

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

Nigerkamg5
Step 1
For a vertex v with a neighbours of degree $\le 5$ and b neihgbours of degree $>5$ we define f(v) as $a/2+b$.
Notice $m=\sum _{v|d\left(v\right)\le 5}^{n}f\left(v\right)$.
Step 2
Let k be the number of vertices of degree $\le 5$.
If $k\le 35$ then clearly $m\le 35\cdot 5=175$.
If $k=35+l$ with $k\in \left\{1,\dots ,5\right\}$ then each summand is at most $5-\frac{l}{2}$ so $\sum _{v|d\left(v\right)\le 5}^{n}f\left(v\right)\le \left(35+l\right)\left(5-\frac{l}{2}\right)<175$.