Graph theory studies networks made of points and connections, such as roads, social networks, circuits, and computer links. This cheat sheet helps students quickly identify graph parts, classify paths and cycles, and use important counting rules. It is useful because many applied math problems can be modeled as vertices connected by edges.
Knowing the basic language makes harder problems easier to organize and solve.
The core ideas include vertices, edges, degree, paths, cycles, connected graphs, trees, and planar graphs. Important formulas include the degree sum formula, Euler's formula for planar graphs, and the tree edge rule. Students should also recognize when Euler paths, Euler circuits, and graph coloring are useful.
These tools help solve routing, scheduling, network design, and map-coloring problems.
Key Facts
- A graph is a set of vertices connected by edges, often written as G = (V, E).
- The degree of a vertex is the number of edges touching it, with a loop counting twice.
- The degree sum formula is sum of all vertex degrees = 2E, where E is the number of edges.
- A path is a sequence of connected vertices, and a cycle is a path that starts and ends at the same vertex without repeating other vertices.
- A connected graph has a path between every pair of vertices.
- A tree is a connected graph with no cycles, and a tree with V vertices has E = V - 1 edges.
- For a connected planar graph, Euler's formula is V - E + F = 2, where F is the number of faces.
- A connected graph has an Euler circuit if every vertex has even degree, and it has an Euler path but not a circuit if exactly two vertices have odd degree.
Vocabulary
- Vertex
- A vertex is a point or node in a graph that represents an object, location, or state.
- Edge
- An edge is a connection between two vertices in a graph.
- Degree
- The degree of a vertex is the number of edges incident to that vertex.
- Path
- A path is a sequence of vertices where each consecutive pair is connected by an edge.
- Tree
- A tree is a connected graph with no cycles.
- Planar Graph
- A planar graph is a graph that can be drawn in a plane without any edges crossing.
Common Mistakes to Avoid
- Counting each edge only once in the degree sum is wrong because every edge contributes 1 degree to each endpoint, so the total degree is 2E.
- Assuming a graph is planar just because one drawing has crossings is wrong because a different drawing may remove the crossings.
- Calling any closed route a cycle is wrong because a cycle cannot repeat vertices except for the starting and ending vertex.
- Using E = V - 1 for every connected graph is wrong because that formula only applies to trees, which must have no cycles.
- Forgetting to check all vertices for Euler circuits is wrong because one odd-degree vertex is enough to prevent an Euler circuit.
Practice Questions
- 1 A graph has 8 vertices with degrees 3, 3, 2, 4, 2, 1, 5, and 4. How many edges does the graph have?
- 2 A connected planar graph has V = 10 vertices and E = 15 edges. How many faces does it have?
- 3 A tree has 18 vertices. How many edges must it have?
- 4 Explain why a road map can be modeled as a graph, and identify what the vertices and edges could represent.
Understanding Graph Theory Basics
A useful first step is deciding what each point and connection represents. In a subway problem, stations may be vertices and tracks may be edges. In a class timetable, courses can be vertices, with an edge when the same students need both courses.
This modeling choice controls the answer. A graph can leave out details such as distance, speed, or cost when they do not matter. When those details do matter, numbers can be attached to edges.
These are called weights. A shortest route in a weighted graph means the route with the smallest total weight, not necessarily the fewest edges.
Degrees give quick information about pressure points in a network. A vertex with a high degree has many direct links, so its failure may affect many other places. A vertex of degree one is an endpoint.
In a tree, removing certain vertices can split the structure into separate parts. These vertices are important in communication networks, family trees, and file systems. The degree sum formula is a strong error check.
Add every degree carefully. The total must be even because each ordinary edge contributes one count at each end. If the total is odd, a degree or edge was missed.
Euler route problems require care about the meaning of travel. They ask for a route that uses every edge once. They do not require visiting every vertex once.
This matches tasks such as street sweeping, snow plowing, or checking each cable in a system. Before drawing routes at random, count the odd-degree vertices. That count tells whether a one-stroke route is possible in a connected network.
If a route is possible but has two odd vertices, it must begin at one odd vertex and finish at the other. A circuit has no separate start and finish because it returns to where it began.
Planarity is about whether edges can be redrawn without crossings, not about the first picture on paper. Moving vertices around is allowed. A crossing only matters if it cannot be removed by redrawing the graph.
For connected planar graphs, count the outside region as a face when using Euler's formula. Graph coloring solves conflict problems. Neighboring vertices must receive different colors, while vertices with no edge between them may share a color.
Colors can represent exam periods, radio frequencies, or work shifts. Start with vertices that have many neighbors, since they create the most restrictions. A valid coloring is not always the coloring that uses the fewest colors, so students should distinguish finding one workable answer from proving that fewer colors cannot work.