Graph Properties and Examples
Important graph properties include connectivity, being a tree (connected without cycles, with exactly n − 1 edges), being Eulerian (a closed walk using every edge once, possible when the graph is connected and all degrees are even), being bipartite (no odd cycles), being planar (drawable without crossings, so that E ≤ 3V − 6 for V ≥ 3) and the chromatic number. In brief: the Königsberg bridges graph has the degrees 3, 3, 3, 5, all odd, so no walk crosses each bridge exactly once. K5 has 10 edges but a planar graph on 5 vertices has at most 9, so K5 is not planar.
Beyond the basic vocabulary of graph theory, the interest lies in properties that can be tested and in the standard families of graphs. This guide describes the families (complete graphs, cycles, paths, complete bipartite graphs, trees, the Petersen graph), and the properties of connectivity, Euler and Hamilton circuits, bipartiteness, planarity and coloring, with worked examples and a table.
Which graph families are standard?
- The complete graph Kn: all pairs adjacent; n vertices, n(n − 1)/2 edges, degree n − 1.
- The path Pn: n vertices in a line, n − 1 edges.
- The cycle Cn (n ≥ 3): n vertices in a ring, n edges, every degree 2.
- The complete bipartite graph Km,n: two groups of m and n vertices, with every vertex of one group adjacent to every vertex of the other; mn edges.
- A regular graph has all degrees equal; a k-regular graph on n vertices has nk/2 edges (the handshake lemma).
- The Petersen graph: 10 vertices, 15 edges, 3-regular, a classical source of counterexamples.
Example 1: counting edges
K6 has 15 edges. K3,3 has 9 edges and is 3-regular. A 4-regular graph on 7 vertices has 7 · 4/2 = 14 edges. A 3-regular graph on 7 vertices cannot exist, since 7 · 3 is odd.
What are trees?
A tree is a connected graph without cycles. A graph on n vertices is a tree if and only if it is connected with n − 1 edges, if and only if it has no cycles and n − 1 edges, if and only if there is exactly one path between any two vertices. Every tree with at least two vertices has at least two leaves (vertices of degree 1). The tree diagrams of multi-stage experiments are trees in this sense. A spanning tree of a connected graph connects all vertices using the fewest edges; for a weighted graph, the minimum spanning tree (found by Kruskal’s or Prim’s algorithm) gives the cheapest network.
Example 2: a tree
A tree with 10 vertices has 9 edges, and its degree sum is 18. If it has exactly 3 vertices of degree 3 and the others have degrees 1 or 2: leaves L and degree-2 vertices T satisfy 3 + L + T = 10 and 9 + L + 2T = 18, so L + 2T = 9 and L + T = 7, giving T = 2 and L = 5.
When does an Euler circuit exist?
An Euler circuit is a closed walk using every edge exactly once. Euler’s theorem: a connected graph has an Euler circuit if and only if every vertex has even degree. An Euler trail (open walk through every edge once) exists if and only if the graph is connected and has exactly two vertices of odd degree, and it must begin and end at them.
Example 3: the Königsberg bridges
The four land masses of Königsberg were joined by seven bridges. As a multigraph, the degrees are 3, 3, 3 and 5, all odd. There are four odd vertices, so neither an Euler circuit nor an Euler trail exists: the walk across every bridge once is impossible, the first result of graph theory (Euler, 1736).
Example 4: positive cases
Cn has all degrees 2, so it has an Euler circuit. K5 has all degrees 4, so it has one. K4 has all degrees 3, so it has none. The four-vertex graph with the edges AB, AC, BC, CD has two odd vertices (C and D), so it has an Euler trail that begins at C and ends at D, for example C–A–B–C–D.
What are Hamilton cycles?
A Hamilton cycle visits every vertex exactly once and returns to the start. Unlike the Euler case, no simple necessary and sufficient condition is known, and deciding whether one exists is computationally hard. A useful sufficient condition is Dirac’s theorem: if a graph has n ≥ 3 vertices and every degree is at least n/2, it has a Hamilton cycle. Kn and Cn have Hamilton cycles; a path does not. The traveling salesman problem asks for the cheapest Hamilton cycle in a weighted graph.
Example 5: counting Hamilton cycles in Kn
Kn has (n − 1)!/2 distinct Hamilton cycles (fix a starting vertex, order the rest, and divide by 2 for the direction): K4 has 3, K5 has 12, K10 has 181,440. This explosive growth is why the traveling salesman problem is hard.
What are bipartite graphs?
A graph is bipartite if its vertices can be split into two groups with all edges going between the groups. By a theorem of König, this holds exactly when the graph has no cycle of odd length. Even cycles, trees and Km,n are bipartite, while K3 and C5 are not.
Example 6: testing bipartiteness
Color a start vertex red, its neighbors blue, their neighbors red, and so on. If two adjacent vertices get the same color, there is an odd cycle. C6 colors alternately (bipartite); C5 ends with two adjacent vertices of the same color (not bipartite).
What are planar graphs?
A graph is planar if it can be drawn in the plane without crossing edges. For a connected planar drawing with V vertices, E edges and F faces (the unbounded one included), Euler’s formula states V − E + F = 2. It implies E ≤ 3V − 6 for V ≥ 3, and E ≤ 2V − 4 if there are no triangles. Kuratowski’s theorem: a graph is planar if and only if it has no subdivision of K5 or K3,3.
Example 7: K5 and K3,3 are not planar
K5: V = 5, E = 10 > 3 · 5 − 6 = 9, so it is not planar. K3,3: V = 6, E = 9, and 9 ≤ 12, so the first bound does not exclude it; but K3,3 has no triangles (it is bipartite), so E ≤ 2V − 4 = 8, and 9 > 8: not planar. Check Euler’s formula on a cube: V = 8, E = 12, F = 6 and 8 − 12 + 6 = 2 ✓.
How does graph coloring work?
A proper coloring assigns colors to vertices so that adjacent vertices differ; the chromatic number χ(G) is the smallest number of colors needed. Bounds: χ(G) ≤ Δ + 1, where Δ is the maximum degree; χ(Kn) = n; χ = 2 for bipartite graphs with at least one edge; the cycle Cn needs 2 colors if n is even and 3 if n is odd. The four color theorem: every planar graph has χ ≤ 4. Coloring models scheduling: vertices are tasks, edges are conflicts, and colors are time slots.
Example 8: scheduling exams
Exams A, B, C, D, with students taking both A and B, A and C, B and C, C and D. This is the graph of the introduction: the triangle ABC needs 3 colors and D can reuse the color of A or B. So 3 time slots suffice and are necessary: χ = 3.
Table of graph families
| Graph | Vertices | Edges | Planar | Chromatic number | Euler circuit |
|---|---|---|---|---|---|
| K4 | 4 | 6 | yes | 4 | no |
| K5 | 5 | 10 | no | 5 | yes |
| C5 | 5 | 5 | yes | 3 | yes |
| C6 | 6 | 6 | yes | 2 | yes |
| K3,3 | 6 | 9 | no | 2 | no |
| tree on n vertices | n | n − 1 | yes | 2 | no |
Where do these results come from?
Euler solved the Königsberg bridge problem in 1736 and proved the polyhedron formula V − E + F = 2 in 1750s. The Hamilton cycle is named after William Rowan Hamilton, who marketed a puzzle based on it (the Icosian game) in 1857. Kuratowski proved his planarity criterion in 1930. The four color conjecture, posed in 1852, was proved in 1976 by Kenneth Appel and Wolfgang Haken with extensive computer assistance.
Which mistakes are common?
Confusing Euler and Hamilton
Euler circuits traverse every edge once and have a clean degree test. Hamilton cycles visit every vertex once and have no simple test.
Forgetting connectivity
Even degrees guarantee an Euler circuit only for connected graphs.
Applying E ≤ 3V − 6 as a criterion for planarity
The inequality is only necessary. K3,3 satisfies it and is still not planar.
Counting the outer face incorrectly
Euler’s formula counts the unbounded outer region as a face.