Introduction to Graphs
A graph is a mathematical structure used to model relationships between objects. Graphs are fundamental in computer science, mathematics, and many real-world applications.
Informal Definition
A graph consists of:
- Vertices (nodes): Objects or entities
- Edges (links): Connections or relationships between vertices
Visual Representation
Example Graph:
v1 ---- v2
| |
| |
v3 ---- v4Vertices: v1, v2, v3, v4 Edges: (v1,v2), (v1,v3), (v2,v4), (v3,v4)
Formal Definition
Undirected Graph
A graph G = (V, E) consists of:
- V: A non-empty set of vertices (or nodes)
- E: A set of edges, where each edge is an unordered pair {u, v} with u, v ∈ V
Example:
- V = {1, 2, 3, 4}
- E = {{1,2}, {1,3}, {2,4}, {3,4}}
Directed Graph (Digraph)
A directed graph G = (V, E) consists of:
- V: A set of vertices
- E: A set of directed edges (ordered pairs)
- Each edge is (u, v) where u is the source and v is the destination
Example:
- V = {1, 2, 3}
- E = {(1,2), (2,3), (3,1)}
Visual:
1 → 2
↑ ↓
← 3Basic Terminology
Adjacent Vertices
Two vertices u and v are adjacent if there is an edge connecting them.
Example: In {1,2}, vertices 1 and 2 are adjacent.
Incident Edge
An edge e = {u, v} is incident to vertices u and v.
Degree of a Vertex
Definition: The degree of a vertex v, denoted deg(v), is the number of edges incident to it.
Example:
Graph:
1 ---- 2
| |
3 ---- 4
|
5- deg(1) = 2 (connected to 2 and 3)
- deg(2) = 2 (connected to 1 and 4)
- deg(3) = 3 (connected to 1, 4, and 5)
- deg(4) = 2 (connected to 2 and 3)
- deg(5) = 1 (connected to 3)
In-degree and Out-degree (Directed Graphs)
In-degree (deg⁻(v)): Number of edges coming into v Out-degree (deg⁺(v)): Number of edges going out from v
Example:
1 → 2 → 3
↑ ↓
←←←←←←←- deg⁺(1) = 1, deg⁻(1) = 1
- deg⁺(2) = 1, deg⁻(2) = 1
- deg⁺(3) = 1, deg⁻(3) = 1
Handshaking Theorem
Theorem: In any undirected graph, the sum of all vertex degrees equals twice the number of edges.
Formula: ∑ deg(v) = 2|E|
Where:
- ∑ deg(v) = sum of all vertex degrees
- |E| = number of edges
Why? Each edge contributes 2 to the total degree (one for each endpoint).
Example
Graph:
1 --- 2
| × |
3 --- 4Edges: {1,2}, {1,3}, {2,4}, {3,4}, {2,3}
Degrees:
- deg(1) = 2
- deg(2) = 3
- deg(3) = 3
- deg(4) = 2
Sum: 2 + 3 + 3 + 2 = 10 Edges: 5 Check: 2 × 5 = 10 ✓
Corollary: Odd-Degree Vertices
Theorem: In any graph, the number of vertices with odd degree is even.
Proof:
- Sum of degrees = 2|E| (always even)
- Sum of even degrees = even
- Therefore, sum of odd degrees must be even
- Only possible if there’s an even number of odd-degree vertices
Example: Cannot have exactly 3 vertices with odd degree!
Real-World Graph Models
1. Social Networks
Model: People as vertices, friendships as edges
Example - Facebook:
- V = {Alice, Bob, Charlie, Diana}
- E = {(Alice, Bob), (Bob, Charlie), (Charlie, Diana), (Diana, Alice)}
Type: Undirected graph (friendship is mutual)
Applications:
- Friend recommendations
- Community detection
- Influence propagation
2. Road Networks
Model: Intersections as vertices, roads as edges
Example - City Map:
- V = {Intersection A, B, C, D}
- E = {(A,B,5km), (B,C,3km), (C,D,4km)}
Type: Weighted graph (edge weights = distances)
Applications:
- GPS navigation
- Traffic routing
- Delivery optimization
3. Web Graph
Model: Web pages as vertices, hyperlinks as directed edges
Example:
- V = {page1.html, page2.html, page3.html}
- E = {(page1 → page2), (page2 → page3), (page3 → page1)}
Type: Directed graph
Applications:
- PageRank algorithm
- Web crawling
- SEO analysis
4. Computer Networks
Model: Computers/routers as vertices, connections as edges
Example - LAN:
- V = {Computer1, Computer2, Switch, Router}
- E = {(Computer1, Switch), (Computer2, Switch), (Switch, Router)}
Applications:
- Network topology design
- Routing protocols
- Fault detection
5. Task Scheduling
Model: Tasks as vertices, dependencies as directed edges
Example - Software Build:
- V = {Compile, Link, Test, Deploy}
- E = {(Compile → Link), (Link → Test), (Test → Deploy)}
Type: Directed acyclic graph (DAG)
Applications:
- Project management
- Build systems
- Course prerequisites
Handshaking Theorem Applications
Example 1: Finding Number of Edges
Problem: A graph has 6 vertices with degrees: 2, 2, 3, 3, 4, 4. How many edges?
Solution:
- Sum of degrees = 2 + 2 + 3 + 3 + 4 + 4 = 18
- Using ∑ deg(v) = 2|E|
- 18 = 2|E|
- |E| = 9 edges
Example 2: Validating Degree Sequence
Problem: Can we have a graph with degrees: 3, 3, 3, 3, 3?
Solution:
- Sum = 15 (odd!)
- But 2|E| must be even
- Impossible! Cannot create such a graph.
Types of Graphs (Overview)
Simple Graph
- No self-loops
- No multiple edges between same vertices
Multigraph
- Allows multiple edges between vertices
- No self-loops
Pseudograph
- Allows both self-loops and multiple edges
Weighted Graph
- Edges have associated weights/costs
Key Points for Exams
- Graph G = (V, E) where V = vertices, E = edges
- Degree of vertex = number of incident edges
- Handshaking Theorem: ∑ deg(v) = 2|E|
- Odd-degree vertices always come in even numbers
- Directed graph has ordered pairs (u,v) as edges
- In-degree + Out-degree for directed graphs
- Applications: social networks, roads, web, scheduling
- Adjacent vertices connected by an edge
- Incident edge touches a vertex
- Cannot have odd sum of degrees
Practice Problems
-
A graph has 6 vertices with degrees 2, 2, 3, 3, 4, 4. How many edges does it have?
-
Can a graph have exactly 5 vertices with odd degree? Why or why not?
-
In a directed graph with 10 vertices, what is the maximum number of edges?
-
Give three real-world examples of graphs not mentioned above
-
If a graph has 15 edges and all vertices have degree 3, how many vertices are there?
-
Draw a graph representing your daily commute. What do vertices and edges represent?
-
A social network has 100 users, and each user has exactly 10 friends. How many friendships (edges) are there?
-
Can you have a graph where the sum of all degrees is 17? Explain.
-
In a tournament where every team plays every other team once, how many games are played with 8 teams?
-
Model a family tree as a graph. Should it be directed or undirected?