Zoom Room 
ToDoodles 
Calculator 
|
Welcome
Zoom Room
ToDoodles
Calculator
|
|
|
| |||||||||||||||||||||||||||
The origins of graph theory are humble, even frivolous.
- N. Biggs, E. K. Lloyd, and R. J. Wilson
A vertex is a dot in a graph.
An edge is a curve (perhaps straight) that starts and end at a vertex.
Can you draw a graph more vertices than edges?
Can you draw a graph more edges than vertices?
An edge that starts and ends at the same vertex is a loop.
The degree of a vertex counts the edges that end there.
Can you draw a graph in which every vertex has degree 2?
Can you draw a graph in which every vertex has degree 3?
A vertex of degree one is a leaf.
Can you draw a graph in which every vertex is a leaf?
Can you draw a graph in which only one vertex is not a leaf?
Two vertices are adjacent if any edges connect them.
Multiple edges connect the same two vertices.
Can you draw a graph with 4 vertices, all of which are adjacent to each other?
Can you draw a graph with 5 vertices, all of which are adjacent to each other?
Can you draw a graph with no loops, multiple edges, 4 vertices, and 6 edges?
Can you draw a graph with loops, no multiple edges, 5 vertices, and 8 edges?
A simple graph has no loops or multiple edges.
Can you draw a simple graph with 6 vertices and 15 edges?
Can you draw a graph with 6 vertices whose degrees are 5, 5, 5, 5, 3, and 3? Does there exist a simple graph of this kind?
Can you draw a graph with 6 vertices whose degrees are 5, 5, 4, 3, 3, and 2? Does there exist a simple graph of this kind?
We can name edges. This lets us describe a walk along adjacent vertices.
Repeating vertices and edges is allowed when on a walk.
Can you find a walk that starts and ends at A that includes E?
Can you find a walk that starts and ends at A that does not include E?
A walk with no edges repeated is a path. (Repeated vertices are still allowed.)
These are the first two of our named graphs, Wheel Four and Wheel Six graphs, which are named after their number of vertices.
Can you draw the Wheel Five graph?
Can you find a path of length 5 on the Wheel Four graph?
Can you find a path of length 9 on the Wheel Six graph?
A walk that ends where it started is a circuit.
This is the Petersen graph.
Can you find different circuits of length 5, 6, 8, and 9 on the Petersen graph?
A tree has no circuits.
I just made up the Dog graph and the Bird graph.
How are leaves and trees related?
Why is a tree called that?
How many different trees can you make with 5 vertices? 6 vertices? 7 vertices?
Show that, in a gathering of 6 people, if there are not three people who all know each other then there are three people none of whom know the other two.
A walk that is both a path and a circuit, and also uses every edge in the graph is a trace.
The House graph is famous.
Can you find a trace on the House graph?
A graph in once piece, whereyou can walk from any vertex to any other, is connected.
Can a graph that is not connected have a path?
Can a graph that is not connected have a circuit?
Can a graph that is not connected have a trace?
An infinite graph keeps going forever.
This is the Infinite Square Grid graph.
Can you draw a connected graph with an infinite number of leaves?
Can you draw an infinite connected graph in which every vertex has degree 3?
Can you find a trace on the infinite square grid?
Can you find a trace on the infinite triangular grid?
Make a chart comparing if a graph has a trace with the numer of vertices with odd degree. Is there a relationship?
A graph that can be drawn or re-drawn without crossings is planar.
Can you invent a graph that is planar but has no trace?
Can you invent a graph that is not planar?
Can you draw the eight corners of a cube as a planar graph?
The graphs with names that we have seen above were the Wheel graphs, the Petersen graph, the Dog and Bird graphs, the House graph, and the Infinite Square Grid.
Which of those graphs with names are planar?
Which of those graphs with names are trees?
Which of those graphs with names have a trace?
For the graphs with names that do not have a trace, how few edges do you need to add to each so it does a trace?
Now you know enough about graph theory to appreciate famous problems, such as the historically important Seven Bridges of Königsberg, or the more recent and amusing Chains of Affection.
The foundation of arithmetic is pairing. A toddler too young to count can prove that two piles of pebbles have different amounts: make pairs by taking one pebble from each pile, and check that one pile runs out before the other. Pairing comes before counting. Pairing does not need numbers.
The foundation of topology is graph theory. A toddler can prove that a flat paper and a donut are different by noticing that on the donut can you draw a planar graph with five vertices, all of which are adjacent to each other—but on a flat paper you cannot. Graph theory also does not need numbers.
