Definition:Path Graph
Jump to navigation
Jump to search
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
This page or section has statements made on it that ought to be extracted and proved in a Theorem page. In particular: Convert these to proofs in Category:Path Graphs. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by creating any appropriate Theorem pages that may be needed. To discuss this page in more detail, feel free to use the talk page. |
- $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$.
- $P_n$ is bipartite for all $n$.
- $P_n$ is a tree for all $n$.
Also see
- Results about path graphs can be found here.