Question: Suppose D is an n-vertex digraph having (n − 2) vertices of outdegree 4 and n vertices of indegree 5. What can you say about the maximum outdegree of D (i.e. the best lower-bound for maximum outdegree of such digraph)?
I think that the answer is: (n/2) + 4
Is this correct?
here is my logic: in digraphs the sum of the outdegree of all vertices must equal the sum of the indegree of all vertices. Therefore, since the sum of the indegree is 5n, the sum of the outdegrees must also equal 5n. Since (n - 2) vertices have a outdegree of 4, then sum of the last two vertices' outdegree must be n + 8. To obtain a lower bound on the highest outdegree is equivalent (I think) to saying that the last two vertices share the same outdegree. And, if they share the same outdegree then we can do following: 5n - 4(n - 2) = total outdegrees left = n + 8. Then split n + 8 among the last two vertices which would be (n/2) + 4