1.) Let G be an n-partite simple graph, the partite sets of which are {ui, vi},...

 

Transcribed Image Text:

1.) Let G be an n-partite simple graph, the partite sets of which are {ui, vi}, {u2, v2}, {un, Un}. Assume that the sequence of degrees d(v₁), d(u2), d(v2),..., d(un-1), d(vn-1), d(un), d(vn) is some permutation of the integers 0, 1, 2, 3,..., 2n - 2. (Note that every vertex except u₁ is listed. Also, by saying "permutation", we are not told which degree goes with which vertex.) Deduce what d(u₁) and d(v₁) are. Justify your answer. (Once you understand what is going on, induction can be an effective way to formulate your proof.) 1.) Let G be an n-partite simple graph, the partite sets of which are {ui, vi}, {u2, v2}, {un, Un}. Assume that the sequence of degrees d(v₁), d(u2), d(v2),..., d(un-1), d(vn-1), d(un), d(vn) is some permutation of the integers 0, 1, 2, 3,..., 2n - 2. (Note that every vertex except u₁ is listed. Also, by saying "permutation", we are not told which degree goes with which vertex.) Deduce what d(u₁) and d(v₁) are. Justify your answer. (Once you understand what is going on, induction can be an effective way to formulate your proof.)

Answer rating: 100% (QA)

To deduce the degrees of vertices u1 and v1 in the npartite simple graph G we can use induction and some observations about the degrees of the vertice... View the full answer