---
title: "Petersen Graph | Combinatorics"
description: "Petersen Graph is a 10-vertex, 15-edge 3-regular graph used in Combinatorics to study bipartite tests, chromatic number, symmetry, and graph structure."
canonical: "https://fiveable.me/combinatorics/key-terms/petersen-graph"
type: "key-term"
subject: "Combinatorics"
unit: "Unit 10"
---

# Petersen Graph | Combinatorics

## Definition

The Petersen graph is a famous 10-vertex, 15-edge graph in Combinatorics. It is 3-regular, non-bipartite, and a standard example for testing graph ideas like coloring, symmetry, and connectivity.

## What It Is

The Petersen graph is one of the most famous graphs in Combinatorics. It has 10 vertices, 15 edges, and every vertex has degree 3, so it is a 3-regular graph. People use it as a compact example of a graph that looks simple but has surprising structure.

A common way to picture it is as two 5-cycles with matching connections between them, or as a graph built from the 2-element subsets of a 5-element set. Different drawings can look very different, but they all represent the same graph up to isomorphism. That is one reason the Petersen graph shows up so often in graph theory, because it is a good reminder that a drawing is not the graph itself.

The graph is not bipartite. The reason is that it contains odd cycles, so you cannot split its vertices into two sets with every edge going between the sets. That makes it a useful counterexample when you are testing whether a graph is bipartite or checking whether a two-color vertex coloring is possible.

Its chromatic number is 3, which means two colors are not enough for a proper vertex coloring, but three colors are. That lines up with its non-bipartite structure. In class, this often shows up when you are asked to color a graph, compare graph families, or explain why a graph cannot be 2-colored.

The Petersen graph is also highly symmetric. Many of its vertices and edges look interchangeable, which makes it a standard example in discussions of graph automorphisms and graph isomorphism. When a graph has that kind of symmetry, you can often spot patterns faster, but you also need to be careful not to assume symmetry guarantees easy properties like bipartiteness or low chromatic number.

A useful mindset is to treat the Petersen graph as a test case. If a statement is supposed to hold for all regular graphs, all non-bipartite graphs, or all graphs with a certain coloring property, the Petersen graph is often one of the first examples worth checking.

## Why It Matters

The Petersen graph matters because it is a compact example that separates graph properties that students often mix together. A graph can be regular without being complete, symmetric without being bipartite, and small without being simple to color. The Petersen graph puts those ideas side by side in one object.

In Combinatorics, that makes it useful for proving or disproving claims. If someone says every 3-regular graph is bipartite, the Petersen graph immediately gives a counterexample. If someone assumes symmetry forces a graph to have chromatic number 2, this graph breaks that idea too.

It also connects directly to the topic of special graphs. You can use it to practice identifying degree patterns, checking whether a graph is bipartite, and finding the chromatic number from structure instead of guessing from a picture. Since it is a named graph with a fixed shape, it often appears in homework, short-answer questions, and proof exercises as a reference point.

The bigger lesson is that graph properties do not always travel together. Regularity, bipartiteness, and colorability are related, but they are not the same thing. The Petersen graph is one of the cleanest examples of that separation.

## Connections

### 3-Regular Graph

The Petersen graph is the classic example of a 3-regular graph because every vertex has degree 3. When you study regular graphs, this one is often the first named example used to show that a graph can have uniform degree without being complete or bipartite. It gives you a concrete model for checking degree counts and spotting regularity from a diagram.

### Chromatic Number

The Petersen graph has chromatic number 3, so it cannot be colored with just two colors. That makes it a good practice graph for vertex-coloring problems, especially when you need to justify why a graph is not 2-colorable. Its coloring behavior also connects to the fact that it contains odd cycles.

### Graph Isomorphism

The Petersen graph can be drawn in more than one way, but different drawings may still represent the same graph. That is where graph isomorphism comes in, because you have to decide whether two pictures preserve the same adjacency pattern. The Petersen graph is a nice example for reminding you to focus on structure, not just appearance.

### [Cage Graphs](/combinatorics/key-terms/cage-graphs)

The Petersen graph often appears in discussions of cage graphs because it is a small, highly structured graph with special degree and girth properties. In that setting, you are looking at how few vertices a graph can have while still meeting certain regularity conditions. The Petersen graph is a standard benchmark for those kinds of extremal questions.

## On the AP Exam

A quiz or problem set might ask you to identify the Petersen graph from a drawing, state its degree sequence, or explain why it is not bipartite. You may also need to give its chromatic number, usually by arguing that odd cycles prevent a 2-coloring but a 3-coloring works. In proof-style questions, it can show up as a counterexample to a false claim about regular graphs or symmetry. If a problem gives you a graph that looks like the Petersen graph, check adjacency carefully, since different drawings can be isomorphic even when they look unfamiliar.

## Petersen Graph vs 3-Regular Graph

The Petersen graph is a specific graph, while a 3-regular graph is any graph where every vertex has degree 3. The Petersen graph is one example in that family, but not every 3-regular graph has the same symmetry, chromatic number, or non-bipartite structure. If a question asks for the Petersen graph, you need the named graph, not just any graph with degree 3 at each vertex.

## Key Takeaways

- The Petersen graph is a specific graph with 10 vertices and 15 edges, not just a general pattern.
- It is 3-regular, so every vertex has degree 3.
- It is not bipartite because it contains odd cycles, which blocks any two-part split of the vertices.
- Its chromatic number is 3, so you need three colors for a proper vertex coloring.
- It is a favorite example in Combinatorics because it is small, symmetric, and full of useful counterexamples.

## FAQs

### What is the Petersen graph in Combinatorics?

The Petersen graph is a famous 10-vertex, 15-edge graph used as a standard example in graph theory. It is 3-regular, non-bipartite, and has chromatic number 3. In Combinatorics, it comes up when you study special graphs, coloring, symmetry, and counterexamples.

### Why is the Petersen graph not bipartite?

A graph is bipartite only if it has no odd cycles. The Petersen graph contains odd cycles, so it cannot be split into two independent sets with every edge crossing between them. That is why it fails the bipartite test.

### What is the chromatic number of the Petersen graph?

Its chromatic number is 3. Two colors are not enough because the graph is not bipartite, but three colors are enough for a proper vertex coloring. This makes it a useful example when you are practicing graph coloring arguments.

### Is the Petersen graph the same thing as a 3-regular graph?

No. The Petersen graph is one specific graph, while 3-regular graph describes a whole family of graphs where every vertex has degree 3. The Petersen graph is a famous member of that family, but many other 3-regular graphs have different shapes and properties.

## 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/petersen-graph#resource","name":"Petersen Graph | Combinatorics","url":"https://fiveable.me/combinatorics/key-terms/petersen-graph","learningResourceType":"Concept explainer","educationalLevel":"AP® / High School","about":{"@id":"https://fiveable.me/combinatorics/key-terms/petersen-graph#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/petersen-graph#term","name":"Petersen Graph","description":"The Petersen graph is a famous 10-vertex, 15-edge graph in Combinatorics. It is 3-regular, non-bipartite, and a standard example for testing graph ideas like coloring, symmetry, and connectivity.","url":"https://fiveable.me/combinatorics/key-terms/petersen-graph","inDefinedTermSet":{"@type":"DefinedTermSet","name":"Combinatorics Key Terms","url":"https://fiveable.me/combinatorics/key-terms"}},{"@type":"FAQPage","mainEntity":[{"@type":"Question","name":"What is the Petersen graph in Combinatorics?","acceptedAnswer":{"@type":"Answer","text":"The Petersen graph is a famous 10-vertex, 15-edge graph used as a standard example in graph theory. It is 3-regular, non-bipartite, and has chromatic number 3. In Combinatorics, it comes up when you study special graphs, coloring, symmetry, and counterexamples."}},{"@type":"Question","name":"Why is the Petersen graph not bipartite?","acceptedAnswer":{"@type":"Answer","text":"A graph is bipartite only if it has no odd cycles. The Petersen graph contains odd cycles, so it cannot be split into two independent sets with every edge crossing between them. That is why it fails the bipartite test."}},{"@type":"Question","name":"What is the chromatic number of the Petersen graph?","acceptedAnswer":{"@type":"Answer","text":"Its chromatic number is 3. Two colors are not enough because the graph is not bipartite, but three colors are enough for a proper vertex coloring. This makes it a useful example when you are practicing graph coloring arguments."}},{"@type":"Question","name":"Is the Petersen graph the same thing as a 3-regular graph?","acceptedAnswer":{"@type":"Answer","text":"No. The Petersen graph is one specific graph, while 3-regular graph describes a whole family of graphs where every vertex has degree 3. The Petersen graph is a famous member of that family, but many other 3-regular graphs have different shapes and properties."}}]},{"@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":"Petersen Graph"}]}]}
```