Heawood 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 Heawood graph is an undirected graph on 14 vertices that can be defined in the following equivalent ways:

1. It is the Levi graph of the Fano plane (which is the projective plane over field:F2).
2. It is the unique (up to graph isomorphism) (3,6)-cage.

Arithmetic functions

Size measures

Function	Value	Explanation
size of vertex set	14	As Levi graph of projective plane over $\mathbb {F} _{q},q=2$: $2(q^{2}+q+1)=2(2^{2}+2+1)=2(7)=14$
size of edge set	21	As Levi graph of projective plane over $\mathbb {F} _{q},q=2$: $(q+1)(q^{2}+q+1)=(2+1)(2^{2}+2+1)=3(7)=21$

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 Levi graph of projective plane over $\mathbb {F} _{q},q=2$: $q+1=3$
eccentricity of a vertex	2	As Levi graph of a projective plane: 2 (using the fact that any two points are incident on a common line, and any two lines are incident on a common point)

Other numerical invariants

Function	Value	Explanation
clique number	2	As a Levi graph, the graph is bipartite, hence triangle-free
independence number	7	Obviously, since the graph is bipartite, we can choose all the vertices on one side as an independent set. It's easy to show that we can do no better in this case.
chromatic number	2	As a Levi graph, the graph is bipartite
radius of a graph	2	Follows from eccentricity of every vertex being 2
diameter of a graph	2	Follows from eccentricity of every vertex being 2
girth of a graph	6	As Levi graph of a projective plane: 6