Path Graphs
Path Graphs
Definition: A Path Graph is a tree that contains only a single path through all of its vertices. |
We denote path graphs by $P_n$ where $n$ refers to the number of vertices in the path graph. For example, some sketches of the path graphs $P_1$, $P_2$, and $P_3$ are provided below:
Note that the number of edges in a path graph is $n-1$. Recall that the number of edges in a tree graph is also $n-1$, and a path graph is a tree graph so this should hold true.
Additionally, a path graph can be obtained from a cycle by removing one of its edges. For example $C_4$ can be transformed into $P_4$ if one of the edges is removed from the graph as the cycle will have been broken.