---
tag: A167XK4YTF
kind: concept
name: Graph theory
msc: [05C99]
sources:
  - url: https://en.wikipedia.org/wiki/Graph_theory
same_as:
  wikidata: Q131476
  wikipedia: Graph theory
---

## Summary

Graph theory is the part of [[combinatorics|0JKW7W7XFR]] that studies [[graphs|00C0BR7D7H]]: sets of vertices joined in pairs by edges.
It asks about paths and cycles, connectivity, colourings, matchings, embeddings in surfaces and the spectra of graph matrices.
Graphs model networks of every kind, so the subject is central in computer science, operations research, chemistry and physics.

## Explanations

### L1 human

A graph is a set of dots with lines between some pairs of dots.
Road maps, social networks and molecules can all be drawn this way.
Graph theory asks questions such as: can one walk over every road exactly once and return home?
Euler answered that question for the bridges of Königsberg in 1736, and this is often seen as the start of graph theory.