Pfadgraph

Pfadgraph, commonly referred to in English as a path graph, is a basic object in graph theory that represents a simple, linear sequence of vertices connected in a single line. Formally, a path graph on n vertices, denoted Pn, has vertex set {v1, v2, ..., vn} and edge set {vivi+1 | i = 1, ..., n−1}. It is the sole graph structure that forms a straight path without branches.

Key properties include: connectivity and acyclicity, making Pn a tree. It contains exactly n−1 edges. The degree sequence consists of two end vertices of degree 1 (for n > 1) and n−2 interior vertices of degree 2 (for n > 2). The diameter of Pn is n−1, and its chromatic number is 2 for n ≥ 2, reflecting its bipartite nature. The automorphism group typically has a small size, often a reflection symmetry exchanging the ends for n ≥ 3.

Pn serves as a fundamental building block in graph theory and algorithm design. It is used as a simple test case for traversal algorithms (such as depth-first and breadth-first search), shortest-path computations on linear structures, and dynamic programming along a chain. It also appears as a baseline graph when evaluating heuristics and complexity in broader graph problems.

Examples: P1 is a single vertex with no edges; P2 is two vertices connected by one edge; P5 consists of five vertices arranged in a straight line with four consecutive edges.

In summary, the Pfadgraph is the canonical representation of a linear sequence in graphs, notable for its simplicity, well-defined properties, and role as a reference model in theory and applications.