Petersen graph

This article defines a particular undirected graph, i.e., the definition here determines the graph uniquely up to graph isomorphism.
View a complete list of particular undirected graphs

Definition

The Petersen graph is a particular undirected graph on 10 vertices that can be defined in the following equivalent ways:

1. It is the complement of the line graph of complete graph:K5.
2. It is the odd graph with parameter 3, i.e., the graph $O_{3}$. Explicitly, this is the Kneser graph $KG_{5,2}$: its vertices are identified with subsets of size two of a 5-element set, and two vertices are adjacent if and only if the corresponding subsets are disjoint.
3. It is the unique 5-cage.

Arithmetic functions

Size measures

Function	Value	Explanation
size of vertex set	10	As $O_{n},n=3$: ${\binom {2n-1}{n-1}}={\binom {5}{2}}=10$
size of edge set	15	As $O_{n},n=3$: ${\frac {1}{2}}{\binom {2n-1}{n-1,n-1,1}}={\frac {1}{2}}{\binom {5}{2,2,1}}=15$

Numerical invariants associated with vertices

Since the graph is a vertex-transitive graph, any numerical invariant associated to a vertex must be equal on all vertices of the graph. Below are listed some of these invariants:

Function	Value	Explanation
degree of a vertex	3	As $O_{n},n=3$: $n=3$
eccentricity of a vertex	2	As $O_{n},n=3$: $n-1=2$

Other numerical invariants

Function	Value	Explanation
clique number	2	As $O_{n},n=3$: 2, since $n\geq 3$
independence number	4	Fill this in later
chromatic number	3
radius of a graph	2	Due to vertex-transitivity, the radius equals the eccentricity of any vertex, which has been computed above.
diameter of a graph	2	Due to vertex-transitivity, the radius equals the eccentricity of any vertex, which has been computed above.
odd girth	5	As $O_{n},n=3$: $2n-1=2(3)-1=5$
even girth	6	As $_{n},n=3$: 6 (we use that $n\geq 3$)
girth of a graph	5	As $O_{n},n=3$: $\min\{2n-1,6\}$