Graph Theory
The ultimate math of connections. Discover the hidden webs that power social media, Google Maps, and video game worlds.
What is a Graph?
Forget bar charts! In this kind of math, a 'graph' is just a bunch of dots (vertices) connected by lines (edges). A map of cities connected by highways is a graph. Your friends list on Discord or Roblox is also a graph!
The Seven Bridges Puzzle
Graph theory started in 1736 with a riddle. A city called Königsberg had seven bridges. The mayor wanted to know: could you walk through the city crossing every bridge exactly once? A mathematician named Euler proved it was impossible, inventing a whole new branch of math to do it.
Coloring the World
Imagine you're drawing a map of the world and don't want any touching countries to be the same color. What's the smallest number of crayons you need? Graph theory proves you only ever need four crayons, no matter how crazy the map is!
Things worth remembering.
The 'Six Degrees of Kevin Bacon' game works because of graph theory.
Google's search engine was built using a giant graph of the internet.
It took a supercomputer to finally prove the Four Color Map Theorem in 1976.
You can use graphs to figure out the fastest way to beat a video game level.
Practice problems.
Try to draw a square with an X inside it without lifting your pencil and without tracing over the same line twice. Can you do it?
Show hint
Count the number of lines connecting to each corner. Euler had a rule about odd and even connections!
Imagine a party with 5 people. Everyone shakes hands with everyone else exactly once. How many handshakes happen?
Show hint
Draw 5 dots in a circle and connect every dot to every other dot. Count the lines!
Can you color a checkerboard using only 2 colors so no touching squares (up/down/left/right) are the same color?
Show hint
You already know what a checkerboard looks like! This is a simple graph coloring problem.
