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
the Petersen graph is typically drawn as a pentagon with a pentagram inside. 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
{\displaystyle O_{3}}
Kneser graph
K
G
5
,
2
{\displaystyle KG_{5,2}}
It is the unique (3,5)-cage . Arithmetic functions Size measures
Function
Value
Explanation
size of vertex set 10
As
O
n
,
n
=
3
{\displaystyle O_{n},n=3}
(
2
n
−
1
n
−
1
)
=
(
5
2
)
=
10
{\displaystyle {\binom {2n-1}{n-1}}={\binom {5}{2}}=10}
size of edge set 15
As
O
n
,
n
=
3
{\displaystyle O_{n},n=3}
1
2
(
2
n
−
1
n
−
1
,
n
−
1
,
1
)
=
1
2
(
5
2
,
2
,
1
)
=
15
{\displaystyle {\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
{\displaystyle O_{n},n=3}
n
=
3
{\displaystyle n=3}
eccentricity of a vertex 2
As
O
n
,
n
=
3
{\displaystyle O_{n},n=3}
n
−
1
=
2
{\displaystyle n-1=2}
Other numerical invariants
Function
Value
Explanation
clique number 2
As
O
n
,
n
=
3
{\displaystyle O_{n},n=3}
n
≥
3
{\displaystyle 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
{\displaystyle O_{n},n=3}
2
n
−
1
=
2
(
3
)
−
1
=
5
{\displaystyle 2n-1=2(3)-1=5}
even girth 6
As
O
n
,
n
=
3
{\displaystyle O_{n},n=3}
n
≥
3
{\displaystyle n\geq 3}
girth of a graph 5
As
O
n
,
n
=
3
{\displaystyle O_{n},n=3}
min
{
2
n
−
1
,
6
}
{\displaystyle \min\{2n-1,6\}}
Graph properties
Property
Satisfied?
Explanation
connected graph Yes
all odd graphs are connected. More generally, all Kneser graphs
K
G
m
,
k
{\displaystyle KG_{m,k}}
k
<
m
/
2
{\displaystyle 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
{\displaystyle KG_{m,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
