# How many edges?

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?

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

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