 TOPICS # Path Graph The path graph is a tree with two nodes of vertex degree 1, and the other nodes of vertex degree 2. A path graph is therefore a graph that can be drawn so that all of its vertices and edges lie on a single straight line (Gross and Yellen 2006, p. 18).

The path graph of length is implemented in the Wolfram Language as PathGraph[Range[n]], and precomputed properties of path graphs are available as GraphData[ "Path", n ]. (Note that the Wolfram Language believes cycle graphs to be path graph, a convention that seems neither standard nor useful.)

The path graph is known as the singleton graph and is equivalent to the complete graph and the star graph . is isomorphic to the complete bipartite graph and to .

Path graphs are graceful.

The path graph has chromatic polynomial, independence polynomial, matching polynomial, and reliability polynomial given by   (1)   (2)   (3)   (4)

where . These have recurrence equations   (5)   (6)   (7)   (8)

The line graph of is isomorphic to . is the Cayley graph of the permutations  2, 1  and  1, 3, 2  .

Cycle Graph, Graceful Graph, Hamiltonian Path, Path, Path Complement Graph, Tree, Triangular Snake Graph

## Explore with Wolfram|Alpha More things to try:

## References

Gross, J. T. and Yellen, J. Graph Theory and Its Applications, 2nd ed. Boca Raton, FL: CRC Press, 2006.

Path Graph

## Cite this as:

Weisstein, Eric W. "Path Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/PathGraph.html