Es sei ${\displaystyle {}G}$ ein linearer Graph mit ${\displaystyle {}n}$ Knotenpunkten. Dann muss in einer Knotenüberdeckung zumindest jeder zweite Knoten (in der natürlichen Reihenfolge auf einem linearen Graphen) vorkommen. Minimale Knotenüberdeckungen sind beispielsweise durch die Knotenfolgen ${\displaystyle {}\{1,3,5,\ldots \}}$ und ${\displaystyle {}\{2,4,6,\ldots \}}$ gegeben, wobei der letzte Knoten, ${\displaystyle {}n-1}$ oder ${\displaystyle {}n}$, davon abhängt, ob ${\displaystyle {}n}$ gerade oder ungerade ist. Bei ${\displaystyle {}n}$ gerade sind beide optimal, bei ${\displaystyle {}n}$ ungerade ist nur die zweite Knotenüberdeckung optimal. Die Knotenüberdeckungszahl beträgt in beiden Fällen ${\displaystyle {}\left\lfloor {\frac {n}{2}}\right\rfloor }$ Knoten. Es gibt aber auch noch ganz andere minimale Knotenüberdeckungen, beispielsweise ${\displaystyle {}\{1,3,4,6,7,9,10\}}$ bei ${\displaystyle {}n=11}$.