Graph theory begins with a deliberately simple idea: draw dots and connect some pairs of dots with lines. The dots are called vertices. The lines are called edges. That sounds almost too small to be serious mathematics, which is exactly why graph theory is such a good COSMO topic.
The point is not that the drawings are impressive. The point is that the drawing lets us remove everything except relationship.
A road map has distances, widths, speed limits, stop signs, and traffic patterns. A graph can ignore all of that and keep only which places are connected. A social network has people, conversations, history, and context. A graph can ignore most of that and keep only who is linked to whom. A schedule has time, priorities, constraints, and preferences. A graph can keep only which tasks depend on other tasks.
Graph theory is the art of deciding that connection is the information worth studying first.
The one-stroke question
A classic starting problem is simple to state: can you trace a drawing without lifting your pencil and without repeating an edge?
Students usually try the drawing first. That is good. The failed attempts matter. After a few minutes, the room begins to notice that some drawings feel possible and others feel impossible. The mathematics starts when we ask what feature separates them.
The key feature is degree. The degree of a vertex is the number of edges touching it.
If you enter a vertex along one edge and leave along another, those two edges pair off. For every internal visit, edges are used in pairs. That means most vertices in a one-stroke route must have even degree. The only possible exceptions are the start and end vertices. The starting point can have one extra exit, and the ending point can have one extra entrance.
So an Euler path can only exist if the graph has exactly 0 or 2 odd-degree vertices. If there are 0 odd vertices, the path can start and end at the same place. If there are 2 odd vertices, the path must start at one odd vertex and end at the other.
This is a proof that comes from movement. We do not need advanced machinery. We need to understand what entering and leaving forces.
Why the rule is powerful
The odd-degree rule does not just help us find routes. It helps us prove that a route cannot exist. That is often a bigger mathematical step for students. Many students are used to math questions having a hidden computation. Graph theory gives them a different kind of answer: “No, and here is why no attempt can work.”
That is proof thinking.
The handshaking lemma gives a related example. If every edge contributes 1 to the degree of each endpoint, then every edge contributes 2 total degrees. Therefore the sum of all vertex degrees is twice the number of edges. In particular, the number of odd-degree vertices must be even.
This means a graph cannot have exactly one odd-degree vertex. It also cannot have exactly three. Before looking at any specific picture, we know something structural must be true.
Trees and minimal connection
A tree is a connected graph with no cycles. Trees are useful because they capture the idea of connection without redundancy.
If a network has a cycle, then at least one edge in that cycle can be removed while the graph remains connected. There is still another way around. But in a tree, every edge matters. Remove one edge and the graph falls into two components.
For a tree with n vertices, the number of edges is always n - 1. This is one of those facts students can discover before proving. Draw trees with 1, 2, 3, 4, and 5 vertices. Count the edges. The pattern appears quickly.
A proof by induction works well here. A tree always has a leaf, which is a vertex of degree 1. Remove a leaf and its one edge; what remains is still a smaller tree. If the smaller tree has n - 2 edges, adding the leaf back gives n - 1 edges.
This connects graph theory with proof techniques. The graph gives the structure; induction explains why the pattern continues.
Graphs as models
A graph is a model, not the full situation. That difference should be explicit.
If we model cities as vertices and roads as edges, we lose road length. If we model friendships as edges, we lose the strength and history of relationships. If we model prerequisites as arrows, we lose the difficulty of each task. A model is useful because it leaves things out carefully.
This is an important applied-math lesson. Students should not learn that math magically solves reality. They should learn that math can clarify one layer of reality, and then we must ask what the model ignored.
A COSMO activity
Give students a campus map, a bus route map, or a made-up network. Ask them to answer four questions:
- Which vertices have the highest degree?
- Is there an Euler path?
- Which edges are bridges, meaning removing them disconnects the graph?
- If you had to add one edge to make the network more reliable, where would it go?
The last question has no single clean answer. That is the point. Students need to explain their choice. They might add an edge between two busy areas, or they might protect a fragile bridge, or they might shorten a common route. Graph theory gives language for the discussion.
What students should leave with
Students should leave knowing the vocabulary: vertex, edge, degree, path, cycle, connected, tree, bridge. But vocabulary is not the goal. They should also leave with the feeling that a drawing can carry an argument.
A graph is not just a picture. It is a way of making relationships visible enough to reason about.