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:

It is the complement of the line graph of complete graph:K5.
It is the odd graph with parameter 3, i.e., the graph $O_{3}$ . Explicitly, this is the Kneser graph $K G_{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.
It is the unique (3,5)-cage.

Arithmetic functions

Size measures

Function	Value	Explanation
size of vertex set	10	As $O_{n}, n = 3$ : $(\binom{2 n - 1}{n - 1}) = (\binom{5}{2}) = 10$
size of edge set	15	As $O_{n}, n = 3$ : $\frac{1}{2} (\binom{2 n - 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$ : $2 n - 1 = 2 (3) - 1 = 5$
even girth	6	As $O_{n}, n = 3$ : 6 (we use that $n \geq 3$ )
girth of a graph	5	As $O_{n}, n = 3$ : $min {2 n - 1, 6}$

Graph properties

Property	Satisfied?	Explanation
connected graph	Yes	all odd graphs are connected. More generally, all Kneser graphs $K G_{m, k}$ are connected for $k < m / 2$ .
regular graph	Yes	all odd graphs, and more generally all Kneser graphs, are regular
vertex-transitive graph	Yes	all odd graphs, and more generally all Kneser graphs, are vertex-transitive
strongly regular graph	Yes	This follows on account of it being a Kneser graph of the form $K G_{m, 2}$ , i.e., the key is that the subset sizes are 2
edge-transitive graph	Yes
symmetric graph	Yes
distance-transitive graph	Yes
self-complementary graph	No	The degree is 3 and the number of vertices is 10. For the graph to be self-complementary, a necessary condition is that the number of vertices should be 1 + twice the degree
cubic graph	Yes	The degree of every vertex is 3, as computed above.
bridgeless graph	Yes
cage	Yes
snark	Yes