Petersen Graph

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 is the Petersen Graph?

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 the Petersen Graph matters in COMBINATORICS

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.

How the Petersen Graph connects across the course

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

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.

Is the Petersen Graph on the COMBINATORICS 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.

The 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 things to remember about the Petersen Graph

• 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.

Frequently asked questions about the Petersen Graph

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.