Mathwords logoReference LibraryMathwords

Graph Theory

Graph theory is the branch of mathematics that studies graphs — structures made up of points called vertices connected by lines called edges. It is used to model and analyze networks, relationships, and connections between objects.

Graph theory is a field of discrete mathematics concerned with the properties and applications of graphs. A graph G=(V,E)G = (V, E) consists of a set VV of vertices (also called nodes) and a set EE of edges, where each edge connects a pair of vertices. Graphs can be directed or undirected, weighted or unweighted, and may contain cycles or be acyclic. The discipline provides tools for studying connectivity, shortest paths, coloring problems, and many other structural questions.

Key Formula

G=(V,E)G = (V, E)
Where:
  • GG = the graph
  • VV = the set of vertices (nodes)
  • EE = the set of edges connecting pairs of vertices

Worked Example

Problem: A small network has 4 people: Alice (A), Bob (B), Carol (C), and Dan (D). Alice knows Bob and Carol. Bob knows Carol and Dan. Carol knows Dan. Represent this as a graph and find the degree of each vertex.
Step 1: Identify the vertices. Each person is a vertex.
V={A,B,C,D}V = \{A, B, C, D\}
Step 2: Identify the edges. Each "knows" relationship is an edge.
E={(A,B), (A,C), (B,C), (B,D), (C,D)}E = \{(A,B),\, (A,C),\, (B,C),\, (B,D),\, (C,D)\}
Step 3: Count the degree of each vertex. The degree is the number of edges connected to that vertex.
deg⁡(A)=2,deg⁡(B)=3,deg⁡(C)=3,deg⁡(D)=2\deg(A) = 2, \quad \deg(B) = 3, \quad \deg(C) = 3, \quad \deg(D) = 2
Step 4: Verify using the Handshaking Lemma: the sum of all degrees equals twice the number of edges.
2+3+3+2=10=2×52 + 3 + 3 + 2 = 10 = 2 \times 5
Answer: The graph has 4 vertices and 5 edges. Alice and Dan each have degree 2, while Bob and Carol each have degree 3.

Visualization

Why It Matters

Graph theory is behind many technologies you use every day. Social networks model friendships as graphs, GPS navigation uses graph algorithms to find the shortest route, and internet search engines analyze the web as a massive graph of linked pages. It also appears in scheduling problems, circuit design, and biology — anywhere connections between things matter.

Common Mistakes

Mistake: Confusing a graph in graph theory with a graph of a function on the coordinate plane.
Correction: In graph theory, a graph is a set of vertices and edges representing a network. It is not the same as plotting y=f(x)y = f(x) on an xyxy-plane. Context will usually make the meaning clear.
Mistake: Forgetting that an edge contributes to the degree of both vertices it connects.
Correction: Each edge has two endpoints, so it adds 1 to the degree of each. This is why the sum of all degrees always equals 2∣E∣2|E| (the Handshaking Lemma).

Related Terms

  • Vertex — The fundamental point or node in a graph
  • Edge — A connection between two vertices