triangulierter Graph, ein Graph G, der keinen induzierten Kreis der Länge größer oder gleich Vier enthält.

Gleichbedeutend damit ist die Aussage, daß in G jeder Kreis der Länge größer oder gleich Vier eine Sehne hat.

Ist C = x₀x₁…x_rx₀ ein Kreis des Graphen G mit r ≥ 3, so nennt man eine Kante x_ix_j ∈ K(G) mit \begin{eqnarray}1\lt |i-j|\lt r\end{eqnarray} eine Sehne des Kreises C. Es ist leicht zu sehen, daß jeder induzierte Teilgraph eines chordalen Graphen wieder chordal ist.

Falls eine Ecke s eines Graphen G in genau einer gesättigten Clique H von G enthalten ist, so bezeichnet man s als simpliziale Ecke und nennt dann H Simplex von G.

Im Zusammenhang mit den simplizialen Ecken fand A. Frank 1975 folgende interessante Charakterisierung der chordalen Graphen.

Ein Graph G ist genau dann chordal, wenn jeder induzierte Teilgraph von G entweder eine Clique ist oder zwei nicht adjazente simpliziale Ecken besitzt.

Insbesondere enthält jeder chordale Graph mindestens eine simpliziale Ecke.

Es sei (v₁,v₂,…,v_n) eine Reihenfolge der Eckenmenge E(G) eines gegebenen Graphen G und \begin{eqnarray}{G}_{i}=G[\{{v}_{i},{v}_{i+1},\ldots, {v}_{n}\}]\end{eqnarray} der von den Ecken v_i, v_i+1,…,v_n induzierte Teilgraph für i = 1,2,…,n. Man nennt (v₁, v₂,…, v_n) ein perfektes Eckeneliminationsschema von G, wenn v_i eine simpliziale Ecke von G_i für alle i = 1, 2…,n ist.

Mit Hilfe des obigen Satzes läßt sich eine weitere Charakterisierung der chordalen Graphen nachweisen.

Ein Graph ist genau dann chordal, wenn er ein perfektes Eckeneliminationsschema besitzt.