4
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ So you've shown (by example) that it's possible to achieve $175$ edges. What remains is to prove that you can't satisfy the condition with more edges. $\endgroup$ Jul 16, 2021 at 22:44
  • $\begingroup$ @RobertShore Yes, but I’m not sure how to do that.. :( $\endgroup$ Jul 16, 2021 at 23:25
  • $\begingroup$ If you have 5 vertices in one half, were you saying that all 35 in the other half connect once to each of these 5 vertices? If that were the case, wouldn't you be violating your original rule about there being no more than 5 incident pairs that may share the same vertex? How can you connect those 5 vertices to any more than 25 unique vertices, without connecting more than 5 edges to any vertex? $\endgroup$ Jul 16, 2021 at 23:51
  • 1
    $\begingroup$ @Someloonywithacalculator I believe the question says that any edge has at least ONE endpoint with a degree of at most 5. Therefore, any number of incident pairs (35, in this case) may share a vertex, given than for each pair the OTHER vertex has a degree 5 or less. $\endgroup$ Jul 17, 2021 at 0:03
  • $\begingroup$ Just brainstorming here, but can you make any progress by considering the line graph of $G$? You need to show that this line graph, which has $40$ edges, can't have more than $175$ vertices. $\endgroup$ Jul 17, 2021 at 0:50

1 Answer 1

2
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .