Ein Graph G = ( V , E ) {\displaystyle {}G=(V,E)} heißt linear, wenn es eine Auflistung v 1 , … , v n {\displaystyle {}v_{1},\ldots ,v_{n}} aller Knoten derart gibt, dass die Kantenmenge gleich { v i , v i + 1 } {\displaystyle {}\{v_{i},v_{i+1}\}} , i = 1 , 2 , … , n − 1 {\displaystyle {}i=1,2,\ldots ,n-1} , ist.
