Ladder graph

Ladder graph
The ladder graph L8.
Vertices	2n
Edges	n+2(n-1)
Chromatic number	2
Chromatic index	3 for n>2 2 for n=2 1 for n=1
Properties	Unit distance Hamiltonian Planar Bipartite
Notation	Ln

In the mathematical field of graph theory, the ladder graph L_n is a planar undirected graph with 2n vertices and n+2(n-1) edges.

The ladder graph can be obtained as the Cartesian product of two path graphs, one of which has only one edge: L_n,1 = P_n × P₁. Adding two more crossed edges connecting the four degree-two vertices of a ladder graph produces a cubic graph, the Möbius ladder.

By construction, the ladder graph L_n is isomorphic to the grid graph G_2,n and looks like a ladder with n rungs. It is Hamiltonian with girth 4 (if n>1) and chromatic index 3 (if n>2).

The chromatic number of the ladder graph is 2 and its chromatic polynomial is ${\displaystyle (x-1)x(x^{2}-3x+3)^{(n-1)}}$.