Chapter III - The Case of the Missing Files

Chapter III deals with a particular class of graphs we call interval graphs. These are graphs that represent the intersections of a set of intervals on the real line. A vertex is associated with each interval in the set, and an edge links two vertices when the two corresponding intervals have a common intersection. These are the graphs that make it possible to unmask Duke Densmore's murderer in Claude Berge's novel. The case Manori solves is a bit more complex than the one Claude Berge created, but it uses the same property of interval graphs, meaning there is no cycle of more than three vertices without a shortcut. So there are no squares, pentagons, hexagons and so forth. The presence of squares in a graph corresponding to the suspects' accounts allows Manori to declare Mrs. Tait the culprit. Readers who want to learn more about this type of graph can consult the works by Fishburn and Trotter.

Teaching notes - Interval Graphs

 

• 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

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