For no reason in particular, it occurred to me to wonder if there exist any graphs (simple, connected, undirected) that contain vertices of every possible degree (from 1 to (n-1)). A quick mental check should confirm that such a graph would necessarily have exactly two vertices that share the same degree (by the pigeonhole principle). It wasn’t much trouble to set my computer to search my nine-vertices-or-less database, but as I had set it up rather inefficiently, it was taking a few minutes. While I waited, I tried to construct one myself on paper.
I was interested in finding a nine-vertex graph specifically, since that is the largest order in the database. So we start with nine vertices:
For the first step we can connect the graph by choosing vertex A to be the degree-8 vertex. We can also already mark off vertex B as being the degree-1 vertex, so both A and B are complete at this point:
We’ll let C be the degree-2 vertex, and we can accomplish that by connecting it to D:
Similarly D will be the degree-3 vertex, and connecting D to E accomplishes this nicely:
Now we need vertex E to have 4 edges, so we connect it with F and G:
Once again, we want five edges for F, so we can accomplish this by connecting it to G, H, and J:
But now it doesn’t look like we can make much more progress. Six of our vertices are already locked up, so the best we can do is to connect all of the remaining three, which won’t suffice since we still need vertices of degree six and seven.
This suggested to me that there must not be any graphs of order 9 with degrees 1-8, and that my computer would search through a couple hundred thousand graphs and come up with nothing. I was surprised, then, when the search returned exactly one result:
It’s hard to argue with that. So what did I do wrong? After thinking for a minute, I realized it was the choice of connections in the early steps. For example, instead of connecting C to D, I should have connected both C and D to J. Connecting C to D was wasting an edge, in a way. It might be more clear if we redraw the graph in the previous style:
Another way to arrive at this answer would be to work in the other direction — after connecting A to all the other vertices, we then reason that J needs to be connected to 7 vertices and can’t connect to B, so it must necessarily be connected to all the others. Then make similar arguments for H and G, and by that point I think the graph would already be finished.
I also thought it was interesting that there was exactly one graph that fit the requirements. I quickly had the computer search the smaller graphs, and sure enough, for each order, there is only one maximally irregular graph (a term I had to make up, since I don’t have a graph theorist on hand to learn me some vocab):
I thought of a pretty simple inductive proof that a maximally irregular graph exists for any order, but I have no idea if there ought to always be exactly one. Isomorphism is extremely easy to check on these graphs, so I’ll start searching for a counterexample.
Comments