---
title: "Kneser Graph Coloring Theorem | Combinatorics"
description: "Kneser Graph Coloring Theorem gives the chromatic number of K(n,k) as n - 2k + 2, a core result for graph coloring in Combinatorics."
canonical: "https://fiveable.me/combinatorics/key-terms/kneser-graph-coloring-theorem"
type: "key-term"
subject: "Combinatorics"
unit: "Unit 12"
---

# Kneser Graph Coloring Theorem | Combinatorics

## Definition

The Kneser Graph Coloring Theorem says the chromatic number of the Kneser graph K(n,k) is n - 2k + 2 when n >= 2k. In Combinatorics, it gives an exact coloring rule for a graph built from disjoint k-element subsets.

## What It Is

The Kneser Graph Coloring Theorem is the exact formula for the chromatic number of a Kneser graph, written as χ(K(n,k)) = n - 2k + 2 for n >= 2k. In Combinatorics, that means you do not just know that the graph can be colored, you know the minimum number of colors needed.

A Kneser graph K(n,k) has a vertex for each k-element subset of an n-element set. Two vertices are adjacent when the subsets are disjoint. That adjacency rule is the whole point of the graph, because the coloring problem becomes a question about separating disjoint sets with different colors.

The theorem tells you something surprising: the coloring number grows in a very controlled way as n gets larger, and it drops when k gets larger. For example, K(5,2) has chromatic number 5 - 4 + 2 = 3, so you need three colors. K(6,2) needs four colors. You can see the pattern without listing every vertex by hand.

The condition n >= 2k matters because you need enough elements to even form disjoint k-subsets. If n is smaller, the graph setup breaks down or becomes trivial in ways that do not match the theorem’s statement.

For a combinatorics class, this theorem is a clean example of how graph theory can turn a set-system problem into a coloring problem. The graph is built from combinations, but the conclusion is about color classes and adjacency, so it sits right at the point where counting and graph structure meet.

## Why It Matters

This theorem gives you an exact answer in a topic that often only gives bounds. In vertex coloring, many graphs are hard to color optimally, so a formula like n - 2k + 2 stands out as a rare case where the minimum is known exactly.

It also connects two big ideas in Combinatorics: set systems and graph coloring. When you study Kneser graphs, you are seeing how a family of subsets can be converted into a graph whose edges encode disjointness. That translation shows up again in other problems where you model a counting or arrangement question as a graph.

The theorem is also useful as a benchmark. If you are comparing coloring behavior across graph families, Kneser graphs give a case where the chromatic number can be much larger than you might guess from a small example. That makes it a good example when you are discussing why greedy coloring can miss the optimal answer.

If your course reaches more advanced graph theory, the theorem is one of the first places where a clean combinatorial statement meets deeper proof ideas. Even if you only use the formula, the setup trains you to read graph definitions carefully and track exactly what adjacency means.

## Connections

### Kneser Graph

The theorem is about this graph family specifically. You need the Kneser graph definition first, because the chromatic number formula only makes sense once you know vertices are k-element subsets and edges join disjoint ones. If you confuse the graph with a generic subset graph, the coloring result stops making sense.

### Chromatic Number

This theorem gives the chromatic number of K(n,k) exactly, not just a bound. That makes it a strong example of what chromatic number means in practice, the fewest colors needed so adjacent vertices get different colors. It is one of the cleanest places to see a coloring invariant turned into a formula.

### Vertex Coloring

Vertex coloring is the method used in the theorem’s statement. The whole question is how to assign colors to the vertices of the Kneser graph so disjoint subsets do not share a color. This is a good example of how a coloring problem can encode a structural property of a graph.

### [Adjacent Vertices](/combinatorics/key-terms/adjacent-vertices)

Adjacency here means the two k-subsets are disjoint, which is not the usual spatial idea some people picture first. The theorem depends on that rule, because proper coloring only cares that adjacent vertices get different colors. Understanding the edge rule is the fastest way to avoid mistakes on examples.

## On the AP Exam

A problem set question will usually ask you to identify K(n,k), compute the chromatic number, or explain why two vertices must receive different colors. The move is to read the graph definition carefully, check that n >= 2k, and then apply χ(K(n,k)) = n - 2k + 2. For a small case like K(5,2), you should be able to state that the answer is 3 and connect that to the disjoint-subset rule. If the question gives a picture or a list of subsets, you may need to spot adjacency first before counting colors. In a short written response, it helps to say that vertices are k-subsets and edges represent disjointness, because that shows you know where the formula comes from.

## Key Takeaways

- The Kneser Graph Coloring Theorem gives an exact chromatic number for Kneser graphs: χ(K(n,k)) = n - 2k + 2 when n >= 2k.
- A Kneser graph uses k-element subsets as vertices, and two vertices are adjacent exactly when the subsets are disjoint.
- The theorem is a strong example of vertex coloring in Combinatorics because it turns a set problem into a graph coloring problem.
- The condition n >= 2k matters because the graph is built around the possibility of disjoint k-subsets.
- Small examples like K(5,2) make the formula easier to trust and remember, since the chromatic number comes out to 3.

## FAQs

### What is the Kneser Graph Coloring Theorem in Combinatorics?

It is the theorem that says the chromatic number of the Kneser graph K(n,k) equals n - 2k + 2 when n >= 2k. In other words, it gives the minimum number of colors needed to color the graph’s vertices so adjacent vertices, meaning disjoint k-subsets, do not share a color.

### How do you find the chromatic number of a Kneser graph?

Use the formula χ(K(n,k)) = n - 2k + 2, as long as n >= 2k. First identify n and k from the graph name or setup, then plug them in. For K(7,3), for example, the chromatic number is 7 - 6 + 2 = 3.

### Why are the vertices adjacent in a Kneser graph?

The vertices are adjacent when the two subsets are disjoint. That edge rule is what turns the set-system into a graph coloring problem. If two subsets share an element, they are not adjacent, so they can share a color unless another constraint gets in the way.

### What is a common mistake with Kneser graphs?

A common mistake is assuming adjacency means the subsets overlap. It is the opposite here: edges connect disjoint subsets. Another mistake is forgetting the condition n >= 2k, which is part of the theorem’s statement.

## Related Study Guides

- [12.1 Vertex coloring and chromatic numbers](/combinatorics/unit-12/vertex-coloring-chromatic-numbers/study-guide/aTY5IipUsYGR9WYI)

## 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/kneser-graph-coloring-theorem#resource","name":"Kneser Graph Coloring Theorem | Combinatorics","url":"https://fiveable.me/combinatorics/key-terms/kneser-graph-coloring-theorem","learningResourceType":"Concept explainer","educationalLevel":"AP® / High School","about":{"@id":"https://fiveable.me/combinatorics/key-terms/kneser-graph-coloring-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/kneser-graph-coloring-theorem#term","name":"Kneser Graph Coloring Theorem","description":"The Kneser Graph Coloring Theorem says the chromatic number of the Kneser graph K(n,k) is n - 2k + 2 when n >= 2k. In Combinatorics, it gives an exact coloring rule for a graph built from disjoint k-element subsets.","url":"https://fiveable.me/combinatorics/key-terms/kneser-graph-coloring-theorem","inDefinedTermSet":{"@type":"DefinedTermSet","name":"Combinatorics Key Terms","url":"https://fiveable.me/combinatorics/key-terms"}},{"@type":"FAQPage","mainEntity":[{"@type":"Question","name":"What is the Kneser Graph Coloring Theorem in Combinatorics?","acceptedAnswer":{"@type":"Answer","text":"It is the theorem that says the chromatic number of the Kneser graph K(n,k) equals n - 2k + 2 when n >= 2k. In other words, it gives the minimum number of colors needed to color the graph’s vertices so adjacent vertices, meaning disjoint k-subsets, do not share a color."}},{"@type":"Question","name":"How do you find the chromatic number of a Kneser graph?","acceptedAnswer":{"@type":"Answer","text":"Use the formula χ(K(n,k)) = n - 2k + 2, as long as n >= 2k. First identify n and k from the graph name or setup, then plug them in. For K(7,3), for example, the chromatic number is 7 - 6 + 2 = 3."}},{"@type":"Question","name":"Why are the vertices adjacent in a Kneser graph?","acceptedAnswer":{"@type":"Answer","text":"The vertices are adjacent when the two subsets are disjoint. That edge rule is what turns the set-system into a graph coloring problem. If two subsets share an element, they are not adjacent, so they can share a color unless another constraint gets in the way."}},{"@type":"Question","name":"What is a common mistake with Kneser graphs?","acceptedAnswer":{"@type":"Answer","text":"A common mistake is assuming adjacency means the subsets overlap. It is the opposite here: edges connect disjoint subsets. Another mistake is forgetting the condition n >= 2k, which is part of the theorem’s statement."}}]},{"@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 12","item":"https://fiveable.me/combinatorics/unit-12"},{"@type":"ListItem","position":4,"name":"Kneser Graph Coloring Theorem"}]}]}
```