Is there a simple graph with degree sequence?

So, You’ve Got a Sequence of Numbers… Can You Build a Graph?

Ever wondered if you could actually build a network, a graph, from just a list of numbers? It’s a pretty cool question that pops up a lot when you’re knee-deep in graph theory. Basically, we’re asking: if you have a bunch of numbers representing how many connections each point in your network should have, can you actually make that network?

Let’s break that down a bit.

What’s a Degree Sequence, Anyway?

Okay, imagine you’ve got a bunch of friends. A “simple graph” is like figuring out who’s friends with whom, but with a couple of rules: nobody’s friends with themselves (no self-loops), and you can’t be “double friends” with someone (no multiple edges). The “degree” of a person is just how many friends they have. So, a “degree sequence” is simply a list of how many friends each person has, usually from the most popular to the least.

For instance, if you have five people and their friendships look like this: one person has 3 friends, two people have 2 friends each, one person has 1 friend, and one person is a total loner, your degree sequence would be (3, 2, 2, 1, 0). Simple enough, right?

The real question is: can you always draw a simple “friends” network if I just give you a list of numbers? In other words, is that sequence “graphical”?

The Obvious Stuff (That Still Matters!)

Before we get fancy, there are a few no-brainers to consider:

• Gotta be positive: You can’t have negative friends (at least, not in this math problem!).
• Can’t be too popular: If you have n people, the most friends anyone can have is n – 1 (you can’t be friends with yourself).
• Even Steven: This is a big one. The total number of friendships has to be even. Think about it: every friendship involves two people, so the total has to be a multiple of two.

But here’s the kicker: just because those things are true doesn’t guarantee you can draw the graph. I learned that the hard way when I was trying to model a social network for a project once. I had a sequence that looked right, but I just couldn’t make it work.

Enter Havel-Hakimi: The Graph-Building Algorithm

This is where the Havel-Hakimi algorithm comes to the rescue. Think of it as a step-by-step recipe for building (or proving you can’t build) your graph.

Here’s the gist:

If you manage to whittle the sequence down to all zeros, congratulations! The algorithm shows you how to build the graph.

A Quick Example

Let’s say we have the sequence (4, 2, 2, 2, 0). Can we make a graph?

Uh oh! We got a negative number. That means (4, 2, 2, 2, 0) cannot be the degree sequence of a simple graph.

The Erdős-Gallai Theorem: The Heavy Artillery

If you really want to get serious, there’s the Erdős-Gallai theorem. It’s a super powerful way to check if a sequence is graphical, but honestly, it’s a bit of a beast. It involves a bunch of inequalities and summations, and while it’s mathematically elegant, it’s often easier to just use Havel-Hakimi.

The Takeaway?

So, can you build a graph from any old list of numbers? Nope! But with a few simple checks and the Havel-Hakimi algorithm, you can figure out whether it’s possible. It’s a fundamental problem in graph theory, and it’s super useful for understanding the limitations of networks and connections. And who knows, maybe it’ll even help you understand your own friend network a little better!