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?
-
$\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
$\begingroup$
$\endgroup$
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
- the size of the set $A$ is the maximized,
- the degree of each vertex in $A$ is maximized, and
- 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)$.
