1.3GraphsArisingfromOtherStructures23Fig. 1.16. The incidencee graph of the Fano plane: the Heawood graphthe edge set of G, the intersection graph of (V, F) has as vertices the edges of Gtwo edges being adiacent if they have an end in common. For historical reasonsthis graph is known as the line graph of G and denoted L(G). Figure 1.17 depictsa graph and its line graph.04GL(G)Fig. 1.17. A graph and its line graphIt can be shown that the intersection graph of the Desargues configuration isisomorphic to the line graph of Ks, which in turn is isomorphic to the complementof the Petersen graph (Exercise 1.3.2). As for the Fano plane, its intersection graphis isomorphic to Kz, because any two of its seven lines have a point in common.The definition of the line graph L(G) may be extended to all loopless graphsG as being the graph with vertex set E in which two vertices are joined by just asedges as theiends inGerofWhen V-R and F is a set of closed intervals of R.theintaph.o(V,F) is called an interual graph. Examples of practical situations which give riseto interval graphs can be found in the book by Berge (1973). Berge even wrote adetective story whose resolution relies on the theory of interval graphs; see Berge(1995).It should be evident from the above examples that graphs are implicit in awide variety of structures. Many such graphs are not only interesting in their ownright but also serve to provide insight into the structures from which they arise1.3 Graphs Arising from Other Structures 23 1234567 124 235 346 457 156 267 137 Fig. 1.16. The incidence graph of the Fano plane: the Heawood graph the edge set of G, the intersection graph of (V, F) has as vertices the edges of G, two edges being adjacent if they have an end in common. For historical reasons, this graph is known as the line graph of G and denoted L(G). Figure 1.17 depicts a graph and its line graph. 1 2 4 3 12 24 23 34 G L(G) Fig. 1.17. A graph and its line graph It can be shown that the intersection graph of the Desargues configuration is isomorphic to the line graph of K5, which in turn is isomorphic to the complement of the Petersen graph (Exercise 1.3.2). As for the Fano plane, its intersection graph is isomorphic to K7, because any two of its seven lines have a point in common. The definition of the line graph L(G) may be extended to all loopless graphs G as being the graph with vertex set E in which two vertices are joined by just as many edges as their number of common ends in G. When V = R and F is a set of closed intervals of R, the intersection graph of (V, F) is called an interval graph. Examples of practical situations which give rise to interval graphs can be found in the book by Berge (1973). Berge even wrote a detective story whose resolution relies on the theory of interval graphs; see Berge (1995). It should be evident from the above examples that graphs are implicit in a wide variety of structures. Many such graphs are not only interesting in their own right but also serve to provide insight into the structures from which they arise