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?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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
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)$.