Click image to open full size
Graph Theory Basics Cheat Sheet
A printable reference covering vertices, edges, degree, paths, trees, planarity, Euler paths, and graph coloring for grades 10-12.
Related Tools
Related Labs
Related Worksheets
Related Infographics
Study as Flashcards
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.