mxty42ued

Answered

2022-11-17

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.

Answer & Explanation

Nigerkamg5

Expert

2022-11-18Added 20 answers

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

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get your answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?