gibt eine notwendige und hinreichende Bedingung dafür, daß ein gegebener Graph der Kantengraph eines anderen Graphen ist.

Präzise formuliert hat J.Krausz im Jahre 1943 folgenden Charakterisierungssatz bewiesen.

Ein Graph G ist genau dann der Kantengraph eines Graphen H, also G ≅ L(H), wenn sich G in kantendisjunkte Cliquen S₁, S₂, …, S_q so zerlegen läßt, daß jede Ecke von G zu höchstens zwei dieser Cliquen gehört.

Besitzt G eine solche Cliquenzerlegung S₁, S₂, …, S_q, so läßt sich der Graph H wie folgt konstruieren. Ist U ⊆ E(G) die Menge aller Ecken, die in genau einer Clique S_i für i = 1, 2, …, q liegen, so besteht E(H) aus U und der Menge S = { S₁, S₂, …, S_q}. Die Kantenmenge von H setzt sich aus der Vereinigung der beiden Mengen \begin{eqnarray}{K}_{1}(H)=\{{S}_{i}{S}_{j}|E({S}_{i})\cap E({S}_{j})\ne 0,i\ne j\}\end{eqnarray}

und \begin{eqnarray}{K}_{2}(H)=\{x{S}_{i}|x\in U\text{und}x\in E({S}_{i})\}\end{eqnarray}

zusammen.

Eine weitere wichtige Charakterisierung der Kantengraphen gelang L.W. Beineke 1968 durch 9 verbotene induzierte Teilgraphen, und 1994 reduzierte L. Soltés die Anzahl dieser verbotenen induzierten Teilgraphen auf 7, falls der Graph mindestens 9 Ecken besitzt.