My last post where I introduced the idea of maximally irregular graphs ended with a question — can there be two distinct (non-isomorphic) maximally irregular graphs of the same order? I had found this not to be the case up to order 9, but of course we can’t be sure that there aren’t any without a formal proof.
Within minutes of publishing the first post, I started getting ideas of how such a proof might go, but I didn’t have the opportunity and the will to formalize it until just recently.
First a lemma to simplify a bit. For a graph of n nodes containing all degrees from 1 to (n-1), there will always be one duplicate degree, and I didn’t specify in my definition which degree it might be. So the first thing we should note is that, for orders greater than 3, it can’t be of degree (n-1) OR of degree 1. It can’t be of degree (n-1), because that would mean there are two vertices connected to every other vertex, which demands that every vertex have degree at least 2, which precludes the existence of a vertex of degree 1, which we require. The duplicate can’t be of degree 1 either, because then there are two vertices that are only connected to the one vertex of maximal degree, which precludes the existence of a vertex of degree (n-2), which must necessarily be connected to all but one vertex. So for a large enough graph (> 3 vertices, so that 1≠(n-2)), there will be one unique vertex of degree (n-1), and one unique vertex of degree 1.
Having established that, we can outline the proof. The proof will be one of infinite descent, which will create a contradiction when combined with our observation that only one maximally irregular graph exists for each order less than ten. So given two distinct graphs of order n, we will construct two distinct graphs of order (n-2).
So we assume the existence of two non-isomorphic graphs on n vertices, G and H. Then we construct G’ and H’ by taking the induced subgraph that results from removing the vertices of degree 1 and (n-1) from each graph. All we have to show is that G’ and H’ are maximally irregular for order (n-2), and that they cannot be isomorphic.
To show that they are maximally irregular, consider what happens to the remaining vertices when the largest and smallest degree vertices are removed, as in the example order-15 graph below:
The degree-1 vertex was only connected to the degree-(n-1) vertex, and so its removal does not change the degrees of any of the remaining vertices. The degree-(n-1) vertex, however, was connected to every remaining vertex, and so removing it will decrement the degree of every remaining vertex. So this subset of vertices in the original graph had degrees in the range [2,(n-2)], and so decrementing each of them gives vertices of degrees [1,(n-3)], which is exactly the requirements for a maximally irregular graph of order (n-2).
All that remains is to show that G’ and H’ cannot be isomorphic. We can do this by contradiction — if G’ and H’ are isomorphic, then we can show that G and H must be isomorphic as well, contradicting our original assumption that they are distinct. To show this, let us assume we have a bijection between the vertices of G’ and H’ — I claim that if we use this same bijection for G and H, adding that the vertices of degree (n-1) are mapped to each other and the vertices of degree 1 are mapped to each other, that it will be an isomorphism. This should be obvious once we note that for the degree (n-1) vertices, all other vertices are connected to them, so they are trivially equivalent; and for the degree-1 vertices, they are only connected to the degree (n-1) vertices, which are mapped to each other. So the connections between the two graphs are preserved.
And that’s it. Given any two distinct maximally irregular graphs of the same order, we can produce two smaller distinct maximally irregular graphs by removing two vertices from each graph. This process can be repeated as many times as necessary to produce two distinct maximally irregular graphs of order less than or equal to nine, and we have searched exhaustively to be sure that these do not exist. Therefore, for every order >= 2, there is one unique maximally irregular graph, so we can speak of the maximally irregular graph for any given order.
As a reward for anybody who actually read this far, I supply images of the maximally irregular graphs on 25, 50, 75, and 100 nodes.
Comments