--- title: "Degree Sequence Reconstruction Problem | Combinatorics" description: "Degree Sequence Reconstruction Problem in Combinatorics asks whether a list of degrees can come from a simple graph, using parity, graph rules, and reconstruction checks." canonical: "https://fiveable.me/combinatorics/key-terms/degree-sequence-reconstruction-problem" type: "key-term" subject: "Combinatorics" unit: "Unit 10" --- # Degree Sequence Reconstruction Problem | Combinatorics ## Definition The degree sequence reconstruction problem asks whether a list of nonnegative integers can be the degree sequence of a simple graph. In combinatorics, you use graph rules like the Handshaking Lemma and construction tests to check if it works. ## What It Is The degree sequence reconstruction problem in combinatorics asks a very specific question: given a list of vertex degrees, can you build a simple graph that has exactly those degrees? If the answer is yes, the list is called graphical. If not, the list breaks one of the rules that real graphs have to follow. A degree sequence is just the list of degrees of the vertices, usually written in nonincreasing order. For example, a graph with degrees 3, 3, 2, 2, 2 can be compared against the rules for simple graphs. Since simple graphs have no loops and no multiple edges, every degree must be at most n - 1, where n is the number of vertices. That means a list can fail before you even try to draw it. The fastest check is the Handshaking Lemma. The sum of all degrees must be even, because every edge contributes 2 to the total degree count. If the sum is odd, the sequence cannot come from any simple graph. That is a quick elimination step, but it does not prove a sequence is graphical by itself. To actually reconstruct a graph, you often use a process like Havel-Hakimi. The idea is to sort the sequence, remove the largest degree, and subtract 1 from the next largest entries that many times. If this process ends in all zeros, the sequence works. If you ever get a negative number or impossible demand, the sequence is not graphical. This problem connects directly to special graph families. A complete graph has a very rigid degree sequence, where every vertex has degree n - 1. A regular graph has the same degree repeated across all vertices, so reconstruction is simpler than for irregular graphs. Bipartite graphs add another layer, since the two parts have degree patterns that must fit the edge structure between the sets. One useful way to think about the problem is that you are reverse-engineering a graph from its local data. The degrees tell you how connected each vertex is, but not who is connected to whom. That is why different graphs can share the same degree sequence, even though the sequence still has to obey strict combinatorics rules. ## Why It Matters This term shows up whenever you move from counting edges to asking whether a proposed graph can actually exist. In combinatorics, that is a common skill: you are not just checking numbers, you are checking whether the numbers can come from a valid structure. The degree sequence reconstruction problem also gives you a bridge between abstract graph properties and actual graph construction. If a problem gives you a degree list, you may need to decide whether to draw a graph, prove it is impossible, or explain why more than one graph could fit. That is a very different kind of reasoning from memorizing a graph definition. It also connects directly to special types of graphs. If a sequence is all the same number, you are probably looking at a regular graph. If one sequence comes from a complete graph, the pattern is rigid and easy to spot. If a graph is bipartite, the degree list has to be consistent with the split between the two partite sets, so the reconstruction process becomes more constrained. You will also see this idea in proof-style questions and problem sets that ask you to justify a yes or no answer. The best response is usually not just “it works” or “it does not work,” but a chain of checks: parity, size bounds, and a reconstruction method like Havel-Hakimi. That makes this term a useful checkpoint for whether you really understand graph structure, not just graph vocabulary. ## Connections ### Degree Sequence A degree sequence is the input list you are trying to analyze, while the reconstruction problem asks whether that list can come from a simple graph. If you can read a degree sequence well, you can start spotting impossible cases faster. This is the first thing to sort, because every later check depends on the exact list and its order. ### Havel-Hakimi Algorithm Havel-Hakimi is the main step-by-step method for testing whether a degree sequence is graphical. It repeatedly removes the largest degree and reduces the next entries, which turns the abstract question into a process you can follow on paper. If the algorithm ends at all zeros, the sequence works. ### Regular Graph Regular graphs are a special case where every vertex has the same degree, so reconstruction is much simpler than for a mixed sequence. If a sequence is constant, you can often test it by looking at the number of vertices and whether the degree value is even feasible. This makes regular graphs a good comparison point for the general problem. ### [Graphical Sequences](/combinatorics/key-terms/graphical-sequences) A graphical sequence is exactly a degree sequence that can be realized by some simple graph. The reconstruction problem is the test for graphicality. When a sequence fails, you are usually identifying which graph condition breaks, such as parity or a degree that is too large. ## On the AP Exam A problem set or quiz question usually gives you a list like 4, 3, 3, 2, 2, 1 and asks whether it is graphical. Your job is to check the basic constraints first, especially whether the sum is even and whether any degree is too large for the number of vertices. Then you may run Havel-Hakimi to confirm the result. If the class asks for a construction, you try to build a simple graph that matches the list, often by connecting the highest-degree vertex first. If it asks for impossibility, you explain which rule fails instead of just saying no. On written work, a clean answer usually includes the sorted sequence and the reduction steps so the reasoning is visible. For special graph sections, the term can also show up in short-response questions about complete, regular, or bipartite graphs. Then you are not just checking a random list, you are matching the degree pattern to the graph type and explaining why it fits or does not fit. ## Degree Sequence Reconstruction Problem vs Degree Sequence A degree sequence is the list of degrees itself. The degree sequence reconstruction problem is the question of whether that list can actually come from a simple graph, and sometimes how to build one. So one is the data, and the other is the test or task you do with that data. ## Key Takeaways - The degree sequence reconstruction problem asks whether a list of nonnegative integers can be realized as the degrees of a simple graph. - A quick first check is the Handshaking Lemma, because the sum of all degrees must be even. - A list can still fail even if the sum is even, so you often need a reconstruction method like Havel-Hakimi. - Different graphs can share the same degree sequence, so the answer is about existence, not uniqueness. - Special graph types like regular and complete graphs have very structured degree sequences that are easier to recognize. ## FAQs ### What is the degree sequence reconstruction problem in combinatorics? It is the problem of deciding whether a given degree list can come from a simple graph. You use graph rules like the Handshaking Lemma and reconstruction methods to test the list. In many problems, you also decide whether you can actually draw one matching graph. ### How do you know if a degree sequence is possible? Start by checking whether the sum of the degrees is even and whether any degree is bigger than n - 1 for a graph with n vertices. Then use a method like Havel-Hakimi to see if the sequence reduces to all zeros. An even sum alone does not guarantee it works. ### What is the difference between a degree sequence and a graphical sequence? A degree sequence is just the list of vertex degrees. A graphical sequence is a degree sequence that can actually be realized by a simple graph. The reconstruction problem is the test that decides whether the list is graphical. ### Can two different graphs have the same degree sequence? Yes, and that is very common. The degree sequence tells you how many edges touch each vertex, but not which vertices are connected to each other. That is why the reconstruction problem is about possibility, not a unique graph. ## Related Study Guides - [10.4 Special types of graphs (bipartite, complete, regular)](/combinatorics/unit-10/special-types-graphs-bipartite-complete-regular/study-guide/aqAFpNKhvgysTllC) ## About This Document Canonical Fiveable pages are available as Markdown at the same path plus `.md`. - [llms.txt](https://fiveable.me/llms.txt): index of Fiveable's sections and URL patterns - [llms-full.txt](https://fiveable.me/llms-full.txt): complete subject and unit listing - [MCP server](https://fiveable.me/mcp): call Fiveable as tools instead of fetching pages (`https://fiveable.me/api/mcp`) - [MCP server for AP teachers](https://fiveable.me/mcp/teachers): a teacher's classes, assignments and AP-rubric grading (`https://fiveable.me/api/mcp/teacher`) ## Structured Data ```json {"@context":"https://schema.org","@graph":[{"@type":"LearningResource","@id":"https://fiveable.me/combinatorics/key-terms/degree-sequence-reconstruction-problem#resource","name":"Degree Sequence Reconstruction Problem | Combinatorics","url":"https://fiveable.me/combinatorics/key-terms/degree-sequence-reconstruction-problem","learningResourceType":"Concept explainer","educationalLevel":"AP® / High School","about":{"@id":"https://fiveable.me/combinatorics/key-terms/degree-sequence-reconstruction-problem#term"},"audience":{"@type":"EducationalAudience","educationalRole":"student"},"dateModified":"2026-07-03T02:21:06.613Z","isPartOf":{"@type":"Collection","name":"Combinatorics Key Terms","url":"https://fiveable.me/combinatorics/key-terms"},"publisher":{"@type":"Organization","name":"Fiveable","url":"https://fiveable.me"}},{"@type":"DefinedTerm","@id":"https://fiveable.me/combinatorics/key-terms/degree-sequence-reconstruction-problem#term","name":"Degree Sequence Reconstruction Problem","description":"The degree sequence reconstruction problem asks whether a list of nonnegative integers can be the degree sequence of a simple graph. In combinatorics, you use graph rules like the Handshaking Lemma and construction tests to check if it works.","url":"https://fiveable.me/combinatorics/key-terms/degree-sequence-reconstruction-problem","inDefinedTermSet":{"@type":"DefinedTermSet","name":"Combinatorics Key Terms","url":"https://fiveable.me/combinatorics/key-terms"}},{"@type":"FAQPage","mainEntity":[{"@type":"Question","name":"What is the degree sequence reconstruction problem in combinatorics?","acceptedAnswer":{"@type":"Answer","text":"It is the problem of deciding whether a given degree list can come from a simple graph. You use graph rules like the Handshaking Lemma and reconstruction methods to test the list. In many problems, you also decide whether you can actually draw one matching graph."}},{"@type":"Question","name":"How do you know if a degree sequence is possible?","acceptedAnswer":{"@type":"Answer","text":"Start by checking whether the sum of the degrees is even and whether any degree is bigger than n - 1 for a graph with n vertices. Then use a method like Havel-Hakimi to see if the sequence reduces to all zeros. An even sum alone does not guarantee it works."}},{"@type":"Question","name":"What is the difference between a degree sequence and a graphical sequence?","acceptedAnswer":{"@type":"Answer","text":"A degree sequence is just the list of vertex degrees. A graphical sequence is a degree sequence that can actually be realized by a simple graph. The reconstruction problem is the test that decides whether the list is graphical."}},{"@type":"Question","name":"Can two different graphs have the same degree sequence?","acceptedAnswer":{"@type":"Answer","text":"Yes, and that is very common. The degree sequence tells you how many edges touch each vertex, but not which vertices are connected to each other. That is why the reconstruction problem is about possibility, not a unique graph."}}]},{"@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"name":"Combinatorics","item":"https://fiveable.me/combinatorics"},{"@type":"ListItem","position":2,"name":"Key Terms","item":"https://fiveable.me/combinatorics/key-terms"},{"@type":"ListItem","position":3,"name":"Unit 10","item":"https://fiveable.me/combinatorics/unit-10"},{"@type":"ListItem","position":4,"name":"Degree Sequence Reconstruction Problem"}]}]} ```