Suppose I have a number of airports which have a set number of routes. Large airports have 7, medium airports have 4, and small airports have 1.

First of all, what would I call a graph of this type where it is undirected, has no parallel edges, no loops, and every edge is connected to another (that is no route goes unused)?

Second of all, how can I determine if I get a number number of airports if it'll work / is connected? Example: 1 large, 3 medium, and 7 small will produce a connected graph but that same combination with 8 small will not.

I'm writing a computer program and looking for a simple way to determine (using some theorem or whatnot) if it works or not. I've attached an image below of what I'm searching for.


  • 3
    $\begingroup$ "What do I call a graph of this type?", it is commonly referred to as a Simple Graph. What have you tried so far? Where did you get stuck? What if you try looking at a simple example; imagine we only have medium and small airports, how do would you test that a set of small and medium airports is valid/connected? Then try adding in large airports after you solve that. $\endgroup$ – ryan Jun 23 '17 at 4:52
  • $\begingroup$ I've done some more research and learned about the handshake theorem, so the sum of the degrees must be even. I've also found out that while there are a few ways to disqualify graphs from being complete, there's not a perfect way (aside from brute force) to determine if a graph is complete or not from the degree sequence alone - if I am not mistaken. $\endgroup$ – Seth Killian Jun 23 '17 at 6:27
  • $\begingroup$ Your problem is a special case of the Graph realization problem. I would look into the Erdos-Gallai theorem. You're specific case of degrees (7, 4, 1) might have some significance and possibly can be solved more easily than using pre-existing solutions though. $\endgroup$ – ryan Jun 23 '17 at 7:00
  • $\begingroup$ @SethKillian: Isn't a complete graph characterized by the degree sequence $(|V|-1, \ldots, |V|-1)$? $\endgroup$ – md5 Jun 23 '17 at 11:37
  • $\begingroup$ @md5, based on the context, I would assume he meant connected rather than complete. $\endgroup$ – ryan Jun 23 '17 at 16:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.