Graphs!

The Seven Bridges of Königsberg

The Seven Bridges of Königsberg is the following famous historical problem solved by Leonhard Euler in 1735. This is the problem that started graph theory.

"The city of Königsberg in Prussia (now Kaliningrad, Russia) was set on both sides of the Pregel River, and included two large islands which were connected to each other and the mainland by seven bridges.

The problem was to find a walk through the city that would cross each bridge once and only once. The islands could not be reached by any route other than the bridges, and every bridge must have been crossed completely every time (one could not walk halfway onto the bridge and then turn around to come at it from another side)."

(The quotation and the image are from the Wikipedia page Seven Bridges of Königsberg)

{{{id=89| /// }}} {{{id=68| /// }}} {{{id=67| /// }}} {{{id=20| /// }}} {{{id=83| /// }}}

Graph Editor

{{{id=84| /// }}} {{{id=86| /// }}} {{{id=88| /// }}} {{{id=87| /// }}} {{{id=19| /// }}} {{{id=17| /// }}}

Spectrum of a graph

The spectrum of a graph is the set of eigenvalues of the adjacency matrix of the graph. 

Question: if G and H are graphs with the same spectrum, then G = H?

Exercise: Use the command graphs(n), which generates all the graphs on $n$ vertices up to isomorphism,  to test whether there are two graphs with less than 7 vertices that have the same spectrum.

{{{id=69| /// }}} {{{id=16| /// }}} {{{id=15| /// }}} {{{id=14| /// }}} {{{id=71| /// }}} {{{id=70| /// }}} {{{id=72| /// }}} {{{id=13| /// }}} {{{id=90| /// }}}