Definition:Path Graph
From ProofWiki
Definition
A path graph is a tree which has a path which passes through all its vertices.
The path graph with $n$ vertices is denoted $P_n$.
Examples
Basic Properties
- $P_1$ is the edgeless graph $N_1$, and also the complete graph $K_1$.
- $P_1$ is (trivially) Hamiltonian and Eulerian.
- $P_2$ is the complete bipartite graph $K_{1, 1}$, and is $1$-regular.
- $P_3$ is the complete bipartite graph $K_{1, 2}$.
- $P_n$ is semi-Hamiltonian and semi-Eulerian for all $n \ge 2$.
