11 Graph Properties and Applications

Modeling Graph Problems

Graph theory represents a system using vertices for objects and edges for relationships. A graph is written as $G=(V,E)$, where $V$ is the vertex set and $E$ is the edge set.

The first modeling decision is to identify what the practical requirement asks you to cover or arrange:

• Cover every road or connection: consider an Eulerian problem.

• Visit every location or object once: consider a Hamiltonian problem.

• Avoid simultaneous conflicts: consider vertex coloring.

• Pair participants or assign resources: consider matching.

• Draw a network without crossings: consider planarity.

Before applying a theorem, determine whether the graph is directed or undirected, weighted or unweighted, simple or a multigraph, and whether connectivity is required.

Takeaway: Translate the real-world requirement into a graph property before choosing an algorithm.

Eulerian Paths and Circuits

An Eulerian path uses every edge exactly once. An Eulerian circuit is the closed version: it also returns to its starting vertex. These concepts are edge-based, so the key diagnostic is the degree of each vertex.

For a connected undirected graph, the degree test is:

• Every vertex has even degree: an Eulerian circuit exists.

• Exactly two vertices have odd degree: an Eulerian path exists, but no Eulerian circuit exists; the path starts and ends at the odd-degree vertices.

• More than two vertices have odd degree: neither an Eulerian path nor an Eulerian circuit exists.

For example, a connected graph with degrees $3,2,4,3,2$ has exactly two odd-degree vertices. It therefore has an Eulerian path but not an Eulerian circuit.

This result reflects how a route behaves at intermediate vertices: every time the route enters, it must leave, pairing incident edges. Only the starting and ending vertices can have an unpaired entrance or exit.

In route inspection, roads or other required connections are represented by edges. If an Eulerian circuit is unavailable, some edges must be repeated. Finding a shortest closed route that covers every edge at least once is the route-inspection, or Chinese postman, problem.

Takeaway: Use degree parity to test an undirected Eulerian route, and remember that the requirement concerns edges rather than vertices.

Hamiltonian Paths and Cycles

A Hamiltonian path visits every vertex exactly once. A Hamiltonian cycle does the same and returns to its starting point. These structures are vertex-based, so they solve a different type of coverage problem from Eulerian routes.

There is no degree criterion as simple and complete as the Eulerian test for arbitrary Hamiltonian graphs. However, several necessary conditions can disprove a Hamiltonian cycle:

• Every vertex must have degree at least $2$.

• A graph with a cut vertex cannot have a Hamiltonian cycle.

• In a bipartite graph, a Hamiltonian path must alternate between the two parts, so their sizes can differ by at most $1$.

These conditions are not generally sufficient. A graph may satisfy them and still lack a Hamiltonian path or cycle.

In the traveling salesperson problem, vertices represent locations and weighted edges represent travel costs. A feasible tour is a Hamiltonian cycle, and the objective is to minimize the total edge weight. Brute-force search can find an optimum for a small complete graph, while greedy methods such as nearest neighbor are faster but may be nonoptimal.

Takeaway: Use Hamiltonian structures when every vertex must be visited once, and do not confuse this with the edge coverage required by an Eulerian structure.

Planarity and Plane Embeddings

A planar graph can be drawn in the plane without edge crossings except at shared endpoints. A crossing-free drawing is called a plane embedding. The same planar graph may also have drawings that contain crossings.

For a connected plane graph, Euler’s formula relates vertices, edges, and faces:

The face count includes the unbounded exterior region. For a simple connected planar graph with at least three vertices, the edge bound is:

If the graph is also bipartite, it has no odd cycle and the stronger bound is:

These inequalities provide quick nonplanarity tests. For example, $K_{3,3}$ has $|V|=6$ and $|E|=9$. The planar bipartite bound would require:

but $9>8$, so $K_{3,3}$ is nonplanar. The graph $K_5$ is another fundamental nonplanar graph.

Kuratowski’s theorem gives a complete characterization: a graph is planar exactly when it contains no subdivision of $K_5$ or $K_{3,3}$.

Takeaway: Use Euler’s formula and planar edge bounds to count regions and identify graphs that cannot be drawn without crossings.

Graph Coloring

A proper vertex coloring assigns a color to every vertex so that adjacent vertices receive different colors. The chromatic number $\chi(G)$ is the minimum number of colors required.

Important examples include:

• For a complete graph, $\chi(K_n)=n$, because every pair of vertices is adjacent.

• A nonempty bipartite graph has chromatic number $2$.

• An odd cycle has chromatic number $3$.

• Every planar graph has chromatic number at most $4$ by the Four Color Theorem.

A greedy coloring algorithm processes vertices in a chosen order and assigns each vertex the lowest-numbered color not used by its already-colored neighbors. It always gives a proper coloring, but the result may use more colors than necessary, and the vertex order can affect the result.

In scheduling, vertices can represent examinations and edges can represent shared students. Adjacent examinations cannot occur simultaneously, so colors represent time slots. The chromatic number is the minimum number of slots required.

The same model applies to radio-frequency assignment, compiler register allocation, and compatible task scheduling. A map can also be converted to a dual graph in which regions become vertices and shared boundaries become edges.

Takeaway: Coloring converts conflict avoidance into a minimum-resource problem: adjacent objects need different labels.

Matchings and Bipartite Assignment

A matching is a collection of pairwise vertex-disjoint edges. Three terms must be distinguished:

• A maximal matching cannot be enlarged by adding another edge.

• A maximum matching has the largest possible number of edges.

• A perfect matching covers every vertex exactly once.

Maximal does not mean maximum. A locally reasonable edge choice may prevent a larger matching that could have been obtained through different choices.

In a bipartite graph, the two vertex parts can represent two kinds of objects, such as workers and jobs. An edge indicates that an assignment is feasible. Hall’s marriage theorem states that a matching covering every vertex in the left part $X$ exists exactly when every subset $S\subseteq X$ has at least as many neighboring vertices as members:

For example, suppose three students have project preferences:

• $A:\{1,2\}$

• $B:\{2,3\}$

• $C:\{1,3\}$

The assignments $A\to 1$, $B\to 2$, and $C\to 3$ form a perfect matching: each student receives one project and each project is used once.

Weighted matching adds a value or cost to each edge. The objective can then be to maximize total value or minimize total cost.

Takeaway: Use matching for one-to-one pairing or assignment, and use Hall’s condition to test whether an entire side can be covered.

Choosing the Right Graph Tool

The same graph concepts support different applications depending on what vertices and edges represent.

• Street inspection: intersections are vertices and roads are edges; covering every road suggests an Eulerian route or route-inspection problem.

• Delivery or sightseeing: locations are vertices and travel connections are edges; visiting every location once suggests a Hamiltonian cycle or the traveling salesperson problem.

• Exam scheduling: exams are vertices and shared students create edges; colors represent time slots.

• Radio-frequency assignment: transmitters are vertices and interference relationships are edges; colors represent frequencies.

• Job assignment: workers and jobs form the two parts of a bipartite graph; edges represent feasible assignments.

• Map or circuit layout: regions or components and their adjacencies can be analyzed using planarity and coloring.

• Communication networks: devices and communication links form graphs used to study connectivity, paths, and spanning structures.

A reliable workflow is:

1. Identify the objects and decide whether each should be a vertex or an edge.

2. Define precisely when two objects are adjacent.

3. Specify whether the graph is directed, undirected, weighted, simple, or a multigraph.

4. Translate the practical requirement into a graph property.

5. Apply a theorem or algorithm only after checking its hypotheses.

The most common modeling error is confusing edge coverage with vertex visitation. “Use every road” and “visit every city once” describe different graph problems even when both involve routes.

Final takeaway: Graph theory becomes effective when the representation preserves the structure of the original task and the selected theorem matches the resulting graph.