The birth of graph theory

Tivadar Danka small portrait Tivadar Danka
Graph theory

Understanding math will make you a better engineer.

So, I am writing the best and most comprehensive book about it.

Taking a walk can change the course of science.

Roaming the streets of Königsberg, Euler was working on a simple puzzle: can he cross each of the city's bridges exactly once? The answer was no. And so, graph theory was born.

At the time of Euler, the central part of Königsberg (now Kaliningrad) was split into four parts by the Pregel (now Pregolya) river, with seven bridges between them, as illustrated below.

The seven bridges of Königsberg

The question is, can you cross each one exactly once during a single walk?

To answer this question, we don't have to study the particular geography and layout of Königsberg, only the islands and the bridges connecting them. By stripping away all unnecessary details, we end up with a few nodes connected by edges. This was the first graph.

The Königsberg graph

After getting rid of the noise, we can listen to the signal. This way, Euler discovered a simple criteria that solved his problem: to traverse all edges exactly once in a single walk, either

  • all nodes must have even edges,
  • or all nodes must have even edges except two.

Since all five nodes of Königsberg's graph have an odd number of edges, we cannot cross each bridge exactly once.

The Königsberg graph

And so, graph theory was born.

Abstraction is one of the strengths of scientific thinking. By trimming unnecessary features, we obtain models that can fit to a wide array of problems.

Without abstraction, our tools would be extremely limited.

Graph theory has fruitful applications in the study of

  • data structures and databases,
  • computer networks and security,
  • sociology,
  • molecular interactions,
  • biochemical pathways,

and much more. Graph theory came a long way from a mathematical puzzle.

Having a deep understanding of math will make you a better engineer.

I want to help you with this, so I am writing a comprehensive book that takes you from high school math to the advanced stuff.
Join me on this journey and let's do this together!