2
$\begingroup$

We have a graph with $n>100$ vertices. For any two adjacent vertices is known that the degree of at least one of them is at most $10$ $(\leq10)$. What is the maximum number of edges in this graph?

|cite|improve this question
$\endgroup$
  • $\begingroup$ should it say 'the degree of at least one of them is at most $10$' ? $\endgroup$ – Rustyn Jan 28 '13 at 9:21
  • $\begingroup$ Can you just use a tree? $\endgroup$ – Bombyx mori Jan 28 '13 at 9:24
  • 1
    $\begingroup$ At least half the vertices have degree at most 10. Try to get an upper bound from this. $\endgroup$ – Louis Jan 28 '13 at 10:19
0
$\begingroup$

Let $A$ be the set of vertices with degree at most 10, and $B$ be the set of vertices with degree at least 11. By assumption, vertices of $B$ are not adjacent to each other. Hence the total number of edges $|E|$ in the graph is equal to the sum of degrees of all vertices in $A$ minus the number of edges connecting two vertices in $A$. Hence $|E|$ is maximized when

  1. the size of the set $A$ is the maximized,
  2. the degree of each vertex in $A$ is maximized, and
  3. the number of edges connecting two vertices in $A$ is minimized.

This means $|E|$ is maximized when the graph is a fully connected bipartite graph, where $|A|=n-10$ and $|B|=10$. The total number of edges of this graph is $10(n-10)$.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy