Path A path in a digraph is a sequence of vertices from one vertex to another using the arcs . The length of a path is the number of arcs used, or the number of vertices used minus one. A simple path cannot visit the same vertex twice. A closed path has the same first and last vertex. In a simple path all the x i are distinct.
Path is used by some authors to mean a simple chain in a graph.
Pendant Vertex A vertex of degree 1. Also known as a leaf . Perfect Matching In a graph with 2n vertices, a matching with n edges is said to be perfect. Every vertex of the graph is saturated by a perfect matching. Another term for a perfect matching is a 1-factor .