Exercise 3 (30 points: In this exercise you will devise an algorithm A that, given two degree sequences, generates a graph with corresponding degrees. That is, the input to A are two integer sequences d = (di, da . . d ".) and q = {q.. . .Yna). The output of A(d, q) s a bipartite graph G(U.KE), such that the number of nodes U, V2 and the nodes in U have degrees di,d2..dn and nodes in V have degrees q1,92,--4n2. (Gs simple, that is, it has no multi-edges.) 1. First, give a necessary and sufficient condition on the sequences d and q that there exist such a graph (ex. There is clearly no graph for the sequences d and g, such that every i we have d 1 and for every J we have q, = 0 ) Prove that the condition is necessary. You will prove that it is sufficient in part 3 of this problem. (7 points) 2. Define the algorithm A and analyze its running time. (10 points) 3. Prove that your algorithm always terminates and, given that the condition in part 1 is fulfilled, always outputs a valid graph. (8 points) 4. Algorithm A takes two sequences as an input. It is a natural question to ask, whether we can also devise an algorithm B that takes only one sequence as input and outputs a general (non-bipartite) graph with the given degree sequence as output? This problem is in fact harder to solve (though, it is still polynomial), and you are not asked to do that. However, give an example that shows that the same algorithmic approach as A does not always work for this case. (e.g. show a graph, such that given its degree sequence, the single partite version of A would not find the corresponding graph. (5 points) Exercise 3 (30 points: In this exercise you will devise an algorithm A that, given two degree sequences, generates a graph with corresponding degrees. That is, the input to A are two integer sequences d = (di, da . . d ".) and q = {q.. . .Yna). The output of A(d, q) s a bipartite graph G(U.KE), such that the number of nodes U, V2 and the nodes in U have degrees di,d2..dn and nodes in V have degrees q1,92,--4n2. (Gs simple, that is, it has no multi-edges.) 1. First, give a necessary and sufficient condition on the sequences d and q that there exist such a graph (ex. There is clearly no graph for the sequences d and g, such that every i we have d 1 and for every J we have q, = 0 ) Prove that the condition is necessary. You will prove that it is sufficient in part 3 of this problem. (7 points) 2. Define the algorithm A and analyze its running time. (10 points) 3. Prove that your algorithm always terminates and, given that the condition in part 1 is fulfilled, always outputs a valid graph. (8 points) 4. Algorithm A takes two sequences as an input. It is a natural question to ask, whether we can also devise an algorithm B that takes only one sequence as input and outputs a general (non-bipartite) graph with the given degree sequence as output? This problem is in fact harder to solve (though, it is still polynomial), and you are not asked to do that. However, give an example that shows that the same algorithmic approach as A does not always work for this case. (e.g. show a graph, such that given its degree sequence, the single partite version of A would not find the corresponding graph. (5 points)
