---
title: "Ore's Theorem | Combinatorics"
description: "Ore's Theorem gives a degree-sum condition that guarantees a Hamiltonian cycle in a simple graph, a fast check in Combinatorics graph theory."
canonical: "https://fiveable.me/combinatorics/key-terms/ores-theorem"
type: "key-term"
subject: "Combinatorics"
unit: "Unit 11"
---

# Ore's Theorem | Combinatorics

## Definition

Ore's Theorem says that a simple graph with n >= 3 has a Hamiltonian cycle if every pair of nonadjacent vertices has degrees that add to at least n. It is a quick sufficient condition in Combinatorics graph theory.

## What It Is

Ore's Theorem is a shortcut for proving that a graph has a Hamiltonian cycle in Combinatorics. Instead of trying every possible route through the vertices, you check a degree-sum condition: for every pair of nonadjacent vertices u and v, deg(u) + deg(v) must be at least n, where n is the number of vertices in the graph.

If that condition holds in a simple graph with at least 3 vertices, then the graph contains a Hamiltonian cycle. A Hamiltonian cycle is a cycle that visits every vertex exactly once and returns to the start. So Ore's Theorem does not just describe a property, it guarantees a specific kind of spanning cycle exists.

The wording about nonadjacent vertices matters. You only look at pairs that are not already connected by an edge. If two vertices are adjacent, Ore's condition says nothing about that pair. That makes the theorem easier to use than trying to inspect every vertex order by hand, because you can focus on the missing edges and the degrees around them.

A simple way to think about the theorem is this: if any two vertices that are missing a direct edge still have enough total connections to the rest of the graph, the graph is dense enough to force a Hamiltonian cycle. The theorem is a sufficient condition, not a necessary one. That means some graphs have Hamiltonian cycles even though they fail Ore's condition.

For example, suppose a graph has 8 vertices. If two nonadjacent vertices have degrees 3 and 5, their sum is 8, so that pair fits the condition. If every nonadjacent pair in the graph works like that, Ore's Theorem lets you conclude the graph is Hamiltonian without constructing the cycle itself. That is why the theorem shows up a lot in proof-based problems about graph structure and cycle existence.

One common mistake is mixing up Hamiltonian and Eulerian ideas. Eulerian circuits depend on edges and vertex parity, while Ore's Theorem is about vertices and a degree-sum rule that forces a Hamiltonian cycle. Another mistake is treating the theorem like an if and only if statement. It is not. It gives a strong yes answer when the condition holds, but failing the condition does not prove the graph is non-Hamiltonian.

## Why It Matters

Ore's Theorem gives you one of the cleanest proof tools in graph theory when a problem asks whether a Hamiltonian cycle must exist. In Combinatorics, that matters because Hamiltonian cycles are often hard to find directly, especially in larger or messier graphs where brute-force checking is not realistic.

The theorem also trains you to read graphs structurally instead of procedurally. You are not listing every route through the graph. You are checking how vertex degrees interact, especially around missing edges, and using that pattern to draw a conclusion about the whole graph.

That kind of reasoning shows up in graph proofs, classification problems, and network questions. If a graph models a route system, a communication network, or a scheduling loop, a Hamiltonian cycle means you can visit every vertex once and return to the start. Ore's condition gives a clean way to justify that such a route exists.

It also connects to broader Hamiltonian theory. Alongside results like Dirac's Theorem and Bondy-Chvátal Theorem, Ore's Theorem is one of the classic degree-based conditions that turns a hard existence question into a checkable inequality. In class, that usually means you are proving a theorem, testing examples, or comparing which graphs meet the condition and which do not.

## Connections

### Hamiltonian Cycle

Ore's Theorem is a sufficient condition for a Hamiltonian cycle to exist. If the degree-sum rule works, you can conclude the graph has a cycle that visits every vertex exactly once and returns to the start. The theorem does not build the cycle for you, but it tells you that one must be there.

### Degree of a Vertex

The whole theorem is built on vertex degrees, so you need to count how many edges touch each vertex correctly. When you test Ore's condition, you focus on nonadjacent pairs and add their degrees. A small counting mistake can flip the conclusion, so degree checking is the main skill behind the theorem.

### [Bondy-Chvátal Theorem](/combinatorics/key-terms/bondy-chvatal-theorem)

Bondy-Chvátal extends the same general idea of forcing Hamiltonian cycles through degree-based conditions. Ore's Theorem is a classic special case in that family. If Ore's condition feels familiar, that's because it sits inside a broader set of results about how graph density can guarantee Hamiltonicity.

### Eulerian Circuit

This is a useful contrast term because Eulerian circuits are about using every edge once, not every vertex once. Ore's Theorem says nothing about edge parity or the existence of an Eulerian circuit. If a problem asks about a route through vertices, you are in Hamiltonian territory, not Eulerian territory.

## On the AP Exam

A quiz or problem set usually gives you a graph and asks whether Ore's Theorem applies. Your job is to check every nonadjacent pair of vertices, compute their degree sums, and compare each sum to n, the number of vertices. If the condition holds for all such pairs, you can state that the graph has a Hamiltonian cycle.

You may also be asked to explain why a graph fails the theorem. In that case, you only need one counterexample pair of nonadjacent vertices whose degrees add to less than n. That does not prove the graph is not Hamiltonian, it only shows Ore's Theorem cannot be used to guarantee one. On proofs and short-answer questions, that distinction is usually what earns the point.

## Ore's Theorem vs Eulerian Circuit

Ore's Theorem is about Hamiltonian cycles, which visit every vertex once. Eulerian circuits are about traversing every edge once. The degree rules are different, so a graph can fail one condition and still satisfy the other.

## Key Takeaways

- Ore's Theorem says a simple graph with n vertices has a Hamiltonian cycle if every pair of nonadjacent vertices has degrees that add to at least n.
- The theorem gives a sufficient condition, not a necessary one, so failing it does not prove the graph is not Hamiltonian.
- You only check pairs of vertices that do not already share an edge, which makes the theorem easier to apply than checking every possible cycle.
- The result is a degree-based shortcut for proving Hamiltonian structure in graph theory problems.
- Do not mix it up with Eulerian ideas, since Ore's Theorem is about visiting vertices, not edges.

## FAQs

### What is Ore's Theorem in Combinatorics?

Ore's Theorem is a graph theory result that guarantees a Hamiltonian cycle in a simple graph if every nonadjacent pair of vertices has a degree sum of at least n, the number of vertices. It is a quick way to prove a graph is Hamiltonian without finding the cycle directly.

### How do you use Ore's Theorem on a graph?

First find n, the number of vertices. Then look at each pair of vertices that are not connected by an edge and add their degrees. If every such pair has a sum of at least n, Ore's Theorem applies and the graph has a Hamiltonian cycle.

### Does Ore's Theorem prove a graph is not Hamiltonian if the condition fails?

No. Ore's Theorem is only a sufficient condition, not a necessary one. A graph can fail the degree-sum test and still have a Hamiltonian cycle, so failure only means the theorem cannot guarantee one.

### What is the difference between Ore's Theorem and a Hamiltonian cycle?

A Hamiltonian cycle is the cycle itself, a route through every vertex exactly once. Ore's Theorem is the rule you check to prove that such a cycle must exist. The theorem is the test, and the cycle is the result.

## Related Study Guides

- [11.2 Eulerian and Hamiltonian paths and cycles](/combinatorics/unit-11/eulerian-hamiltonian-paths-cycles/study-guide/v68bxywk0iOiroOI)

## 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/ores-theorem#resource","name":"Ore's Theorem | Combinatorics","url":"https://fiveable.me/combinatorics/key-terms/ores-theorem","learningResourceType":"Concept explainer","educationalLevel":"AP® / High School","about":{"@id":"https://fiveable.me/combinatorics/key-terms/ores-theorem#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"},"author":{"@type":"Organization","@id":"https://fiveable.me/editorial#content-team","name":"Fiveable Content Team","url":"https://fiveable.me/editorial","parentOrganization":{"@id":"https://fiveable.me/#organization"},"member":[{"@type":"Person","name":"Amanda DoAmaral","sameAs":["https://www.linkedin.com/in/adoamaral"]},{"@type":"Person","name":"Becky Bahr","sameAs":["https://www.linkedin.com/in/becky-bahr-b52743132"]}]},"publisher":{"@type":"Organization","name":"Fiveable","url":"https://fiveable.me"}},{"@type":"DefinedTerm","@id":"https://fiveable.me/combinatorics/key-terms/ores-theorem#term","name":"Ore's Theorem","description":"Ore's Theorem says that a simple graph with n >= 3 has a Hamiltonian cycle if every pair of nonadjacent vertices has degrees that add to at least n. It is a quick sufficient condition in Combinatorics graph theory.","url":"https://fiveable.me/combinatorics/key-terms/ores-theorem","inDefinedTermSet":{"@type":"DefinedTermSet","name":"Combinatorics Key Terms","url":"https://fiveable.me/combinatorics/key-terms"}},{"@type":"FAQPage","mainEntity":[{"@type":"Question","name":"What is Ore's Theorem in Combinatorics?","acceptedAnswer":{"@type":"Answer","text":"Ore's Theorem is a graph theory result that guarantees a Hamiltonian cycle in a simple graph if every nonadjacent pair of vertices has a degree sum of at least n, the number of vertices. It is a quick way to prove a graph is Hamiltonian without finding the cycle directly."}},{"@type":"Question","name":"How do you use Ore's Theorem on a graph?","acceptedAnswer":{"@type":"Answer","text":"First find n, the number of vertices. Then look at each pair of vertices that are not connected by an edge and add their degrees. If every such pair has a sum of at least n, Ore's Theorem applies and the graph has a Hamiltonian cycle."}},{"@type":"Question","name":"Does Ore's Theorem prove a graph is not Hamiltonian if the condition fails?","acceptedAnswer":{"@type":"Answer","text":"No. Ore's Theorem is only a sufficient condition, not a necessary one. A graph can fail the degree-sum test and still have a Hamiltonian cycle, so failure only means the theorem cannot guarantee one."}},{"@type":"Question","name":"What is the difference between Ore's Theorem and a Hamiltonian cycle?","acceptedAnswer":{"@type":"Answer","text":"A Hamiltonian cycle is the cycle itself, a route through every vertex exactly once. Ore's Theorem is the rule you check to prove that such a cycle must exist. The theorem is the test, and the cycle is the result."}}]},{"@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 11","item":"https://fiveable.me/combinatorics/unit-11"},{"@type":"ListItem","position":4,"name":"Ore's Theorem"}]}]}
```