Path Graphs
Table of Contents

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.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License