Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
1  
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

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.