Polytechnique > Quick on the Draw > Chapter IV - The Case of the Hidden Inheritance

Chapter IV - The Case of the Hidden Inheritance

In the case of Mr. Grumbacker's inheritance, Manori proves that the anonymous caller is a crook using graphs called "line graphs". A line graph is a graph of the intersections between the edges of a graph. More specifically, in a given graph, which I'll note as G, we can construct a new graph, H, whose vertices represent the edges of G such that two vertices are linked with an edge in H if, and only if, the two corresponding edges in G have an end in common. One of the first major discoveries in regard to this class of graphs was made by Hassler Whitney (see his work in the bibliography), who succeeded in demonstrating that with few exceptions, we can rebuild the original G graph in a unique way when we know its line graph, H. In 1968, Beineke (see the bibliography) showed that a line graph is characterized by the non-existence of exactly nine sub-graphs. In other words, he built a set of nine graphs which are not line graphs, and was able to demonstrate that in choosing a given subset of vertices in a G line graph and adding all the edges that link these vertices in G, we never obtain any one of the nine graphs in his set. In the inheritance case, Manori realizes that the graph drawn by Bonvin is one of the nine graphs on Beineke's list.

Teaching notes - Line Graphs

 

Top of the page
Home :: Chapter I Respecting the Rules :: Chapter II The Villas of the Bellevue :: Chapter III The Case of the Missing Files :: Chapter IV The Case of the Hidden Inheritance :: Chapter V An Unhappy Employee :: Chapter VI The Case of the Runaway Mouse :: Chapter VII The Case of the Hooded Man :: Chapter VIII The Getaway Car :: Chapter IX The Sudoku Apprentice :: Bibliography