Graph Theory Question

Question

Let G be an n-partite simple graph, the partite classes of which are {u1, v1}, {u2, v2}, . . . , {un, vn}. Assume that the sequence of degrees d(v1), 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 u1 is listed. Also, by saying ‘permutation’, we are not told which degree goes with which vertex.) Deduce what d(u1) and d(v1) are. Justify your answer. (Once you understand what is going on, induction can be an effective way to formulate your proof.)

Answer 1

It looks like there are several deep mathematical ideas that the question refers to, so a potentially helpful first step could be to make sure that all the background concepts are familiar.

Perhaps the most profound concept that is referred to is the Principle of Mathematical Induction.

Induction is an extremely powerful idea that is easily abused through misunderstanding, and must therefore be approached with care (to avoid nonsensical conclusions such as that all horses are gray.) Reviews of varying terseness can be found on Wolfram Mathworld, Encyclopedia Britannica, Wikipedia, and Khan Academy but for now it might suffice to think of induction as a way of making extremely well-justified generalizations, or of proving an enormous number of (sometimes nontrivial) statements from a few simple observations.

Another concept that your question refers to is that of an n - partite graph, definitions for which can be found on either Wikipedia or Wolfram MathWorld: https://mathworld.wolfram.com/k-PartiteGraph.html.

It is also worth noting that the n-partite graph is also simple, meaning that it can have no self- or double-edges.

Finally, a permutation of a set is just a bijection of that set to itself. For example, an equivalent statement to the sequence (d(v₁), d(u₂), d(v₂), . . ., d(u_n), d(v_n)) being a permutation of the integers between 0 and 2n - 2 is that

{d(v₁), d(u₂), d(v₂), . . ., d(u_n), d(v_n)} = {0, . . . , 2n - 2}.

Please note that this is just one way of representing or paraphrasing concepts: readers are invited to invoke their own preferred conceptual framework.

Once the basic concepts have hopefully been elucidated and interpreted faithfully, one can begin to think about how to solve the problem at hand. My goal in the following is not to answer the question directly, but to hopefully present a few ideas that can help interested readers develop their own mathematically rigorous answer. (Apologies in advance if the somewhat procedural approach is tedious.)

The result that we wish to prove falls under the general topic of discrete math. Questions in discrete math tend to involve enumeration, finding correspondences, and to a large extent, mathematical induction. Something to keep in mind in trying to solve (or resolve) discrete math questions, is that often a little bit of progress can go a long way. Because of this, it can be (at times surprisingly) helpful to begin just by experimenting with the structures involved, recognizing or acknowledging simple general results when they exist and examining 'small n' cases (e.g. when n = 1 or n = 2.)

The case n = 1 turns out to be essentially trivial: 2n - 2 = 0, and the unique n-partite simple graph of order 2 with d(v₁) = 0 consists of just two disconnected vertices:

o o

Things start to get more interesting at n = 2. In this case, 2n - 2 = 2, and {d(v₁), d(u₂), d(v₂)} = {0, 1, 2}. Astute readers might observe that d(v₁) cannot be either 0 or 2 (and by process of elimination must therefore be 1.)

The case n = 3 (where 2n - 2 = 4) is substantially messier, although once again, one can see that d(v₁) cannot be either 0 or 4. This last pattern happens to be general: for any n, d(v₁) must be between 1 and 2n - 3 (inclusive.)

Proof: left as an exercise for the reader.

This observation happens to be extremely useful in proving the main result. Another equally simple and useful observation is that at least one other vertex must have degree 2n - 2.

Hopefully those clues don't give away too much. That said, sometimes the greater challenge in math is in making intuition rigorous. Best of luck, and (most importantly) have fun!