Graph Types - Learning Module

Loading content...

0/276

Undirected Graphs — Two-Way Edges

The World of Mutual Connections

Imagine a network of friends where every friendship is mutual—if Alice is friends with Bob, then Bob is automatically friends with Alice. No one-sided relationships exist; every connection goes both ways. This symmetry, where edges have no inherent direction, is the defining characteristic of undirected graphs.

Undirected graphs are the most intuitive graph type, often the first encountered in graph theory. They model relationships that are inherently bidirectional: friendships, physical roads (where you can travel in either direction), electrical connections, and molecular bonds. This symmetry simplifies many analyses while still capturing the essence of connectivity between entities.

What You Will Learn

By the end of this page, you will understand the formal definition and notation of undirected graphs, recognize their natural applications, master fundamental concepts like degree and connectivity, and appreciate how their symmetry enables elegant algorithms. You'll also learn to contrast them with directed graphs to choose the appropriate model for any problem.

Formal Definition and Notation

An undirected graph is a mathematical structure that formalizes symmetric, bidirectional relationships between entities. Unlike directed graphs where edges have a source and target, undirected edges connect two vertices as equals—neither endpoint is privileged.

Formal Definition:

An undirected graph G is defined as an ordered pair G = (V, E), where:

V is a finite set of vertices (also called nodes)
E is a set of edges, where each edge is an unordered pair {u, v} with u, v ∈ V and typically u ≠ v

The crucial distinction from directed graphs is the word unordered. The edge {u, v} is identical to {v, u}—they represent the same connection. If u connects to v, then v connects to u; you cannot have one without the other.

Set Notation for Edges

We use set notation {u, v} for undirected edges because order doesn't matter in sets: {A, B} = {B, A}. This contrasts with ordered pairs (u, v) used in directed graphs where (A, B) ≠ (B, A). This notational difference reflects the fundamental structural difference between the graph types.

Example:

Consider an undirected graph with V = {A, B, C, D} and E = {{A, B}, {A, C}, {B, C}, {C, D}}.

In this graph:

A connects to both B and C
B connects to A and C
C connects to A, B, and D
D connects only to C

Notice how connectivity is mutual. If we can go from A to B, we can always go from B to A. There's no concept of 'one-way' in an undirected graph.

Undirected Graph Terminology
Term	Definition	Example
Edge	An unordered pair {u, v} representing a connection	{A, B} connects A and B bidirectionally
Endpoints	The two vertices connected by an edge	A and B are endpoints of {A, B}
Incident	An edge is incident to its endpoints	{A, B} is incident to both A and B
Adjacent	Two vertices connected by an edge	A and B are adjacent if {A, B} ∈ E
Neighbor	A vertex adjacent to a given vertex	B is a neighbor of A if {A, B} ∈ E
Path	Sequence of vertices connected by edges	A-B-C is a path if {A,B} and {B,C} exist
Cycle	A path that starts and ends at the same vertex	A-B-C-A if {A,B}, {B,C}, {C,A} all exist

Vertex Degree

In undirected graphs, we have a single, elegant concept of degree—the number of edges incident to a vertex. Unlike directed graphs that require in-degree and out-degree, undirected graphs have a unified measure of vertex connectivity.

Definition:

The degree of a vertex v, denoted deg(v), is the number of edges incident to v. Equivalently, it's the number of neighbors of v:

deg(v) = |{e ∈ E : v ∈ e}| = |{u ∈ V : {u, v} ∈ E}|

Special Cases:

A vertex with degree 0 is called isolated (no connections)
A vertex with degree 1 is called a pendant or leaf vertex
A vertex connected to all other vertices has degree |V| - 1

The Handshaking Lemma

The sum of all vertex degrees equals twice the number of edges: Σdeg(v) = 2|E|. This is because each edge contributes 1 to the degree of each of its two endpoints. This fundamental result implies that the number of odd-degree vertices is always even—a useful fact for proving graph properties.

Degree Sequence:

The degree sequence of a graph is the list of all vertex degrees, typically sorted in non-increasing order. This sequence provides a fingerprint of the graph's structure:

A regular graph has all vertices with the same degree (e.g., a 3-regular graph has every vertex with degree 3)
A complete graph K_n has all vertices with degree n-1
A star graph has one high-degree center and all other vertices with degree 1

Not every sequence of non-negative integers is a valid degree sequence. The Erdős–Gallai theorem provides necessary and sufficient conditions for a sequence to be graphical (realizable as a simple graph).

degree_calculation.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
def calculate_degrees(adjacency_list):
    """
    Calculate the degree of each vertex in an undirected graph.
    
    Args:
        adjacency_list: Dict mapping each vertex to its list of neighbors.
                       For undirected graphs, if A is in B's list, B must be in A's list.
    
    Returns:
        Dict mapping each vertex to its degree
    """
    return {vertex: len(neighbors) for vertex, neighbors in adjacency_list.items()}
 
def get_degree_sequence(adjacency_list, sorted_desc=True):
    """
    Get the degree sequence of an undirected graph.
    
    Returns a list of degrees, optionally sorted in descending order.
    """
    degrees = calculate_degrees(adjacency_list)
    sequence = list(degrees.values())
    if sorted_desc:
        sequence.sort(reverse=True)
    return sequence
 
def verify_handshaking_lemma(adjacency_list):
    """
    Verify that sum of degrees equals twice the number of edges.
    This serves as a sanity check for undirected graph representation.
    """
    degrees = calculate_degrees(adjacency_list)
    sum_of_degrees = sum(degrees.values())
    
    # Count edges (each edge counted once in undirected representation)
    # In adjacency list, each edge appears twice (once for each endpoint)
    total_adjacencies = sum(len(neighbors) for neighbors in adjacency_list.values())
    num_edges = total_adjacencies // 2
    
    assert sum_of_degrees == 2 * num_edges, "Handshaking lemma violated!"
    return sum_of_degrees, num_edges
 
def find_vertices_by_degree(adjacency_list, target_degree):
    """
    Find all vertices with a specific degree.
    Useful for finding leaves (degree 1), isolated vertices (degree 0), etc.
    """
    degrees = calculate_degrees(adjacency_list)
    return [v for v, d in degrees.items() if d == target_degree]
 
# Example: Undirected graph
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'C', 'D'],
    'C': ['A', 'B', 'D', 'E'],
    'D': ['B', 'C'],
    'E': ['C']  # E is a pendant vertex (degree 1)
}
 
degrees = calculate_degrees(graph)
print("Degrees:", degrees)
# Output: {'A': 2, 'B': 3, 'C': 4, 'D': 2, 'E': 1}
 
print("Degree sequence:", get_degree_sequence(graph))
# Output: [4, 3, 2, 2, 1]
 
sum_deg, edges = verify_handshaking_lemma(graph)
print(f"Sum of degrees: {sum_deg}, Edges: {edges}")
# Output: Sum of degrees: 12, Edges: 6
 
print("Pendant vertices:", find_vertices_by_degree(graph, 1))
# Output: ['E']

Real-World Applications of Undirected Graphs

Undirected graphs naturally model relationships that are inherently symmetric. When a connection exists, it works equally in both directions. Let's explore the most significant applications across different domains.

Major Application Domains

•Social Networks (Symmetric) — Facebook friendships are undirected: if Alice is friends with Bob, Bob is friends with Alice. Unlike Twitter follows, Facebook friendships require mutual consent. Analyzing these networks reveals friend circles, community structures, and network centrality.
•Road Networks (Bidirectional) — Most roads allow travel in both directions. Intersections are vertices, road segments are edges. This model enables shortest path algorithms for GPS navigation, traffic flow analysis, and infrastructure planning. (One-way streets require directed edges or mixed graphs.)
•Computer Networks — Ethernet connections, peer-to-peer networks, and wireless mesh networks are undirected. If computer A can send to B, B can send to A over the same link. Network topology analysis uses undirected graphs to find bottlenecks, redundant paths, and failure points.
•Molecular Structures — Chemical bonds in molecules are undirected. Atoms are vertices, bonds are edges. Chemists use graph theory to analyze molecular structure, predict properties, and search for substructures (subgraph isomorphism).
•Electrical Circuits — Resistor networks and some circuit analyses use undirected graphs. Components are vertices, wire connections are edges. Kirchhoff's laws and circuit analysis algorithms operate on these graph representations.
•Collaboration Networks — Co-authorship networks, where vertices are researchers and edges connect those who've published together, are undirected. Analyzing these reveals research clusters, influential researchers, and cross-disciplinary bridges.

Undirected Graph Applications Comparison
Domain	Vertices	Edges	Key Questions
Social (symmetric)	Users	Mutual friendships	Community detection, influence
Road Networks	Intersections	Bidirectional roads	Shortest paths, connectivity
Computer Networks	Devices	Communication links	Reliability, routing
Molecular Chemistry	Atoms	Chemical bonds	Structure matching, properties
Electrical Circuits	Components/junctions	Wire connections	Current flow, resistance
Collaboration	Researchers	Co-authorship	Clustering, centrality

Choosing Between Directed and Undirected

Ask yourself: 'If A relates to B, does B necessarily relate to A in the same way?' If yes—use undirected. If not—use directed. In social networks: Facebook = undirected (mutual friendship), Twitter = directed (one-way follows). In roads: most = undirected, one-way streets = directed.

Connectivity and Connected Components

Connectivity is a fundamental property of undirected graphs. Unlike directed graphs where reachability is asymmetric, undirected graphs have a simpler connectivity model—if you can get from A to B, you can always get from B to A.

Definition:

An undirected graph is connected if there exists a path between every pair of vertices. In a connected graph, no vertex is isolated from the rest; you can travel from any vertex to any other.

Connected Components:

A connected component is a maximal set of vertices such that there exists a path between every pair of vertices in the set. The key word is maximal—you cannot add any more vertices while maintaining the path property.

Key Properties:

Every vertex belongs to exactly one connected component
A connected graph has exactly one connected component (the entire graph)
Connected components partition the vertex set

Simpler Than Digraphs

Undirected connectivity is simpler than directed connectivity. Directed graphs require the distinction between 'weakly connected' (ignoring direction) and 'strongly connected' (respecting direction). Undirected graphs have just one connectivity concept—the symmetric nature of edges eliminates this complexity.

Finding Connected Components:

Connected components can be found efficiently using either BFS or DFS:

Start with all vertices unmarked
Pick any unmarked vertex, run BFS/DFS from it
All vertices visited form one connected component
Repeat with remaining unmarked vertices

Alternatively, Union-Find (Disjoint Set Union) provides an efficient online algorithm that can process edges incrementally and answer connectivity queries in near-constant time.

Applications of Connectivity:

Network reliability: Is the network still connected if a node fails?
Image segmentation: Connected pixels of similar color form regions
Social network analysis: Finding isolated communities
Garbage collection: Unreachable objects (disconnected from roots) are garbage

connected_components.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
from collections import deque
from typing import Dict, List, Set
 
def find_connected_components_bfs(graph: Dict[str, List[str]]) -> List[Set[str]]:
    """
    Find all connected components using BFS.
    
    Args:
        graph: Adjacency list representation of undirected graph
    
    Returns:
        List of sets, where each set is a connected component
    
    Time Complexity: O(V + E)
    Space Complexity: O(V)
    """
    visited = set()
    components = []
    
    def bfs(start):
        component = set()
        queue = deque([start])
        visited.add(start)
        
        while queue:
            vertex = queue.popleft()
            component.add(vertex)
            
            for neighbor in graph.get(vertex, []):
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        
        return component
    
    for vertex in graph:
        if vertex not in visited:
            component = bfs(vertex)
            components.append(component)
    
    return components
 
def is_connected(graph: Dict[str, List[str]]) -> bool:
    """Check if an undirected graph is connected."""
    components = find_connected_components_bfs(graph)
    return len(components) == 1
 
class UnionFind:
    """
    Disjoint Set Union data structure for efficient connectivity.
    
    Supports:
      - union(u, v): Merge components containing u and v
      - find(u): Find the representative of u's component
      - connected(u, v): Check if u and v are in the same component
    
    Using path compression and union by rank for near O(1) operations.
    """
    def __init__(self, vertices):
        self.parent = {v: v for v in vertices}
        self.rank = {v: 0 for v in vertices}
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # Path compression
        return self.parent[x]
    
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False  # Already in same component
        
        # Union by rank
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True
    
    def connected(self, x, y):
        return self.find(x) == self.find(y)
    
    def get_components(self):
        components = {}
        for v in self.parent:
            root = self.find(v)
            if root not in components:
                components[root] = set()
            components[root].add(v)
        return list(components.values())
 
 
# Example usage
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'C'],
    'C': ['A', 'B'],
    'D': ['E'],
    'E': ['D'],
    'F': []  # Isolated vertex
}
 
components = find_connected_components_bfs(graph)
print(f"Number of components: {len(components)}")
print("Components:", components)
# Output: 3 components: {'A', 'B', 'C'}, {'D', 'E'}, {'F'}
 
print(f"Is connected: {is_connected(graph)}")  # False
 
# Union-Find approach
uf = UnionFind(['A', 'B', 'C', 'D', 'E', 'F'])
for u, neighbors in graph.items():
    for v in neighbors:
        uf.union(u, v)
 
print("Components via Union-Find:", uf.get_components())
print(f"A and C connected: {uf.connected('A', 'C')}")  # True
print(f"A and D connected: {uf.connected('A', 'D')}")  # False

Bridges and Articulation Points

Not all edges and vertices are equally important, for graph connectivity. Some are critical—their removal would disconnect parts of the graph. Identifying these critical elements is essential for network reliability analysis.

Bridge (Cut Edge):

A bridge is an edge whose removal increases the number of connected components. In other words, if you remove this edge, the graph becomes disconnected (or 'more disconnected' if it already had multiple components).

Bridges are single points of failure. In a network, a bridge represents a link with no backup—if it fails, communication between some nodes becomes impossible.

Articulation Point (Cut Vertex):

An articulation point is a vertex whose removal (along with its incident edges) increases the number of connected components. Removing this vertex disconnects the graph.

Articulation points are critical nodes—servers, routers, or people whose removal would fragment the network.

Network Vulnerability

A well-designed network should minimize bridges and articulation points. If your network has many critical edges/vertices, a single failure could cause widespread disconnection. Redundancy (multiple paths between nodes) eliminates these vulnerabilities.

Finding Bridges and Articulation Points:

Tarjan's algorithm finds all bridges and articulation points in O(V + E) time using a single DFS. The key insight is tracking discovery times and low-link values:

Discovery time disc[v]: When vertex v was first visited during DFS
Low-link value low[v]: The minimum discovery time reachable from the subtree rooted at v

Bridge Detection: An edge (u, v) is a bridge if low[v] > disc[u]. This means v cannot reach anything discovered before u except through the edge (u, v)—so removing (u, v) disconnects v's subtree.

Articulation Point Detection: A vertex u is an articulation point if:

u is the DFS root and has two or more children, OR
u is not the root and has a child v where low[v] ≥ disc[u]

bridges_articulation.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
from typing import Dict, List, Set, Tuple
 
def find_bridges_and_articulation_points(
    graph: Dict[str, List[str]]
) -> Tuple[List[Tuple[str, str]], Set[str]]:
    """
    Find all bridges and articulation points using Tarjan's algorithm.
    
    Args:
        graph: Adjacency list of an undirected graph
    
    Returns:
        Tuple of (bridges, articulation_points)
    
    Time Complexity: O(V + E)
    Space Complexity: O(V)
    """
    disc = {}  # Discovery time of each vertex
    low = {}   # Lowest discovery time reachable
    parent = {}  # Parent in DFS tree
    bridges = []
    articulation_points = set()
    timer = [0]  # Using list for mutability in nested function
    
    def dfs(u):
        disc[u] = low[u] = timer[0]
        timer[0] += 1
        children = 0
        
        for v in graph.get(u, []):
            if v not in disc:  # Tree edge
                children += 1
                parent[v] = u
                dfs(v)
                
                # Update low value
                low[u] = min(low[u], low[v])
                
                # Bridge check: v cannot reach anything before u
                if low[v] > disc[u]:
                    bridges.append((u, v))
                
                # Articulation point check (non-root)
                if parent.get(u) is not None and low[v] >= disc[u]:
                    articulation_points.add(u)
                    
            elif v != parent.get(u):  # Back edge (not to parent)
                low[u] = min(low[u], disc[v])
        
        # Root is articulation point if it has 2+ children
        if parent.get(u) is None and children > 1:
            articulation_points.add(u)
    
    # Handle disconnected graphs
    for vertex in graph:
        if vertex not in disc:
            parent[vertex] = None
            dfs(vertex)
    
    return bridges, articulation_points
 
 
# Example: Graph with clear structure
#     A
#    / \
#   B - C - D - E
#           |   |
#           F - G
#
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'C'],
    'C': ['A', 'B', 'D'],
    'D': ['C', 'E', 'F'],
    'E': ['D', 'G'],
    'F': ['D', 'G'],
    'G': ['E', 'F']
}
 
bridges, articulation_points = find_bridges_and_articulation_points(graph)
 
print("Bridges (critical edges):", bridges)
# Output: [('C', 'D')] - removing C-D disconnects {A,B,C} from {D,E,F,G}
 
print("Articulation Points (critical vertices):", articulation_points)
# Output: {'C', 'D'} - removing C or D disconnects the graph
 
# A more vulnerable graph
linear_graph = {
    'A': ['B'],
    'B': ['A', 'C'],
    'C': ['B', 'D'],
    'D': ['C']
}
 
bridges, aps = find_bridges_and_articulation_points(linear_graph)
print("\nLinear graph bridges:", bridges)  # All edges are bridges
print("Linear graph articulation points:", aps)  # B and C

Special Types of Undirected Graphs

Several important families of undirected graphs have special properties that enable efficient algorithms or arise frequently in applications:

Complete Graph (K_n):

A complete graph has an edge between every pair of vertices. With n vertices, it has n(n-1)/2 edges. Every vertex has degree n-1. Complete graphs represent scenarios where everything is directly connected to everything else.

Cycle Graph (C_n):

A cycle graph is a single cycle of n vertices. Each vertex has exactly degree 2. It's the simplest connected graph with no leaves.

Path Graph (P_n):

A path graph is a simple path of n vertices. Two endpoints have degree 1; all internal vertices have degree 2. It's the simplest connected graph structure.

Structural Graph Types

•Tree: Connected graph with no cycles. |E| = |V| - 1. Unique path between every pair.
•Forest: Disjoint union of trees. An acyclic graph (may be disconnected).
•Bipartite Graph: Vertices partition into two sets; edges only between sets, never within.
•Complete Bipartite (K_m,n): Bipartite with all possible edges between the two sets.
•Star Graph: One central vertex connected to all others (K_1,n).

Density-Based Types

•Sparse Graph: |E| = O(|V|). Most real-world networks are sparse.
•Dense Graph: |E| = Θ(|V|²). Approaches complete graph density.
•Planar Graph: Can be drawn on a plane with no edge crossings. By Euler: |E| ≤ 3|V| - 6.
•Regular Graph: Every vertex has the same degree k (called k-regular).
•Random Graph G(n,p): n vertices; each edge included independently with probability p.

Trees Are Special

Trees are perhaps the most important special case of undirected graphs. They're connected but minimally so (removing any edge disconnects them). They have exactly |V| - 1 edges. Every tree is bipartite. Many problems that are hard on general graphs become easy on trees due to their acyclic structure.

Summary: Undirected Graphs

We've explored undirected graphs comprehensively—from their formal definition to practical algorithms and real-world applications. Let's consolidate the key concepts:

Key Takeaways

•Undirected graphs model symmetric relationships — Edge {u, v} means u connects to v AND v connects to u. The relationship is mutual and bidirectional.
•Single degree concept — Unlike directed graphs, undirected graphs have one degree per vertex, counting all incident edges. The Handshaking Lemma states Σdeg(v) = 2|E|.
•Connectivity is simpler — If you can reach v from u, you can reach u from v. No need for 'strongly' vs 'weakly' connected distinctions.
•Connected components partition vertices — Every vertex belongs to exactly one component. BFS/DFS or Union-Find efficiently finds components.
•Bridges and articulation points — Critical edges/vertices whose removal disconnects the graph. Tarjan's algorithm finds them in O(V + E).
•Special graph types — Trees, complete graphs, bipartite graphs, planar graphs—each with unique properties enabling specialized algorithms.

What's Next:

We've mastered both directed and undirected graphs. But edges often carry more information than mere existence—they have weights representing costs, distances, capacities, or strengths. The next page explores weighted graphs, where edges have associated values that fundamentally change the algorithms we use.

Page Complete

You now have a thorough understanding of undirected graphs: their formal definition, degree concepts, connectivity properties, bridges and articulation points, and special types. You can identify when a problem calls for undirected modeling and apply appropriate algorithms effectively.

Undirected Graphs — Two-Way Edges

The World of Mutual Connections

What You Will Learn

Formal Definition and Notation

Formal Definition:

An undirected graph G is defined as an ordered pair G = (V, E), where:

V is a finite set of vertices (also called nodes)
E is a set of edges, where each edge is an unordered pair {u, v} with u, v ∈ V and typically u ≠ v

Set Notation for Edges

Example:

Consider an undirected graph with V = {A, B, C, D} and E = {{A, B}, {A, C}, {B, C}, {C, D}}.

In this graph:

A connects to both B and C
B connects to A and C
C connects to A, B, and D
D connects only to C

Notice how connectivity is mutual. If we can go from A to B, we can always go from B to A. There's no concept of 'one-way' in an undirected graph.

Undirected Graph Terminology
Term	Definition	Example
Edge	An unordered pair {u, v} representing a connection	{A, B} connects A and B bidirectionally
Endpoints	The two vertices connected by an edge	A and B are endpoints of {A, B}
Incident	An edge is incident to its endpoints	{A, B} is incident to both A and B
Adjacent	Two vertices connected by an edge	A and B are adjacent if {A, B} ∈ E
Neighbor	A vertex adjacent to a given vertex	B is a neighbor of A if {A, B} ∈ E
Path	Sequence of vertices connected by edges	A-B-C is a path if {A,B} and {B,C} exist
Cycle	A path that starts and ends at the same vertex	A-B-C-A if {A,B}, {B,C}, {C,A} all exist

Vertex Degree

Definition:

The degree of a vertex v, denoted deg(v), is the number of edges incident to v. Equivalently, it's the number of neighbors of v:

deg(v) = |{e ∈ E : v ∈ e}| = |{u ∈ V : {u, v} ∈ E}|

Special Cases:

A vertex with degree 0 is called isolated (no connections)
A vertex with degree 1 is called a pendant or leaf vertex
A vertex connected to all other vertices has degree |V| - 1

The Handshaking Lemma

Degree Sequence:

The degree sequence of a graph is the list of all vertex degrees, typically sorted in non-increasing order. This sequence provides a fingerprint of the graph's structure:

A regular graph has all vertices with the same degree (e.g., a 3-regular graph has every vertex with degree 3)
A complete graph K_n has all vertices with degree n-1
A star graph has one high-degree center and all other vertices with degree 1

degree_calculation.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
def calculate_degrees(adjacency_list):
    """
    Calculate the degree of each vertex in an undirected graph.
    
    Args:
        adjacency_list: Dict mapping each vertex to its list of neighbors.
                       For undirected graphs, if A is in B's list, B must be in A's list.
    
    Returns:
        Dict mapping each vertex to its degree
    """
    return {vertex: len(neighbors) for vertex, neighbors in adjacency_list.items()}
 
def get_degree_sequence(adjacency_list, sorted_desc=True):
    """
    Get the degree sequence of an undirected graph.
    
    Returns a list of degrees, optionally sorted in descending order.
    """
    degrees = calculate_degrees(adjacency_list)
    sequence = list(degrees.values())
    if sorted_desc:
        sequence.sort(reverse=True)
    return sequence
 
def verify_handshaking_lemma(adjacency_list):
    """
    Verify that sum of degrees equals twice the number of edges.
    This serves as a sanity check for undirected graph representation.
    """
    degrees = calculate_degrees(adjacency_list)
    sum_of_degrees = sum(degrees.values())
    
    # Count edges (each edge counted once in undirected representation)
    # In adjacency list, each edge appears twice (once for each endpoint)
    total_adjacencies = sum(len(neighbors) for neighbors in adjacency_list.values())
    num_edges = total_adjacencies // 2
    
    assert sum_of_degrees == 2 * num_edges, "Handshaking lemma violated!"
    return sum_of_degrees, num_edges
 
def find_vertices_by_degree(adjacency_list, target_degree):
    """
    Find all vertices with a specific degree.
    Useful for finding leaves (degree 1), isolated vertices (degree 0), etc.
    """
    degrees = calculate_degrees(adjacency_list)
    return [v for v, d in degrees.items() if d == target_degree]
 
# Example: Undirected graph
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'C', 'D'],
    'C': ['A', 'B', 'D', 'E'],
    'D': ['B', 'C'],
    'E': ['C']  # E is a pendant vertex (degree 1)
}
 
degrees = calculate_degrees(graph)
print("Degrees:", degrees)
# Output: {'A': 2, 'B': 3, 'C': 4, 'D': 2, 'E': 1}
 
print("Degree sequence:", get_degree_sequence(graph))
# Output: [4, 3, 2, 2, 1]
 
sum_deg, edges = verify_handshaking_lemma(graph)
print(f"Sum of degrees: {sum_deg}, Edges: {edges}")
# Output: Sum of degrees: 12, Edges: 6
 
print("Pendant vertices:", find_vertices_by_degree(graph, 1))
# Output: ['E']

Real-World Applications of Undirected Graphs

Major Application Domains

•Social Networks (Symmetric) — Facebook friendships are undirected: if Alice is friends with Bob, Bob is friends with Alice. Unlike Twitter follows, Facebook friendships require mutual consent. Analyzing these networks reveals friend circles, community structures, and network centrality.
•Road Networks (Bidirectional) — Most roads allow travel in both directions. Intersections are vertices, road segments are edges. This model enables shortest path algorithms for GPS navigation, traffic flow analysis, and infrastructure planning. (One-way streets require directed edges or mixed graphs.)
•Computer Networks — Ethernet connections, peer-to-peer networks, and wireless mesh networks are undirected. If computer A can send to B, B can send to A over the same link. Network topology analysis uses undirected graphs to find bottlenecks, redundant paths, and failure points.
•Molecular Structures — Chemical bonds in molecules are undirected. Atoms are vertices, bonds are edges. Chemists use graph theory to analyze molecular structure, predict properties, and search for substructures (subgraph isomorphism).
•Electrical Circuits — Resistor networks and some circuit analyses use undirected graphs. Components are vertices, wire connections are edges. Kirchhoff's laws and circuit analysis algorithms operate on these graph representations.
•Collaboration Networks — Co-authorship networks, where vertices are researchers and edges connect those who've published together, are undirected. Analyzing these reveals research clusters, influential researchers, and cross-disciplinary bridges.

Undirected Graph Applications Comparison
Domain	Vertices	Edges	Key Questions
Social (symmetric)	Users	Mutual friendships	Community detection, influence
Road Networks	Intersections	Bidirectional roads	Shortest paths, connectivity
Computer Networks	Devices	Communication links	Reliability, routing
Molecular Chemistry	Atoms	Chemical bonds	Structure matching, properties
Electrical Circuits	Components/junctions	Wire connections	Current flow, resistance
Collaboration	Researchers	Co-authorship	Clustering, centrality

Choosing Between Directed and Undirected

Connectivity and Connected Components

Definition:

An undirected graph is connected if there exists a path between every pair of vertices. In a connected graph, no vertex is isolated from the rest; you can travel from any vertex to any other.

Connected Components:

Key Properties:

Every vertex belongs to exactly one connected component
A connected graph has exactly one connected component (the entire graph)
Connected components partition the vertex set

Simpler Than Digraphs

Finding Connected Components:

Connected components can be found efficiently using either BFS or DFS:

Start with all vertices unmarked
Pick any unmarked vertex, run BFS/DFS from it
All vertices visited form one connected component
Repeat with remaining unmarked vertices

Alternatively, Union-Find (Disjoint Set Union) provides an efficient online algorithm that can process edges incrementally and answer connectivity queries in near-constant time.

Applications of Connectivity:

Network reliability: Is the network still connected if a node fails?
Image segmentation: Connected pixels of similar color form regions
Social network analysis: Finding isolated communities
Garbage collection: Unreachable objects (disconnected from roots) are garbage

connected_components.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
from collections import deque
from typing import Dict, List, Set
 
def find_connected_components_bfs(graph: Dict[str, List[str]]) -> List[Set[str]]:
    """
    Find all connected components using BFS.
    
    Args:
        graph: Adjacency list representation of undirected graph
    
    Returns:
        List of sets, where each set is a connected component
    
    Time Complexity: O(V + E)
    Space Complexity: O(V)
    """
    visited = set()
    components = []
    
    def bfs(start):
        component = set()
        queue = deque([start])
        visited.add(start)
        
        while queue:
            vertex = queue.popleft()
            component.add(vertex)
            
            for neighbor in graph.get(vertex, []):
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        
        return component
    
    for vertex in graph:
        if vertex not in visited:
            component = bfs(vertex)
            components.append(component)
    
    return components
 
def is_connected(graph: Dict[str, List[str]]) -> bool:
    """Check if an undirected graph is connected."""
    components = find_connected_components_bfs(graph)
    return len(components) == 1
 
class UnionFind:
    """
    Disjoint Set Union data structure for efficient connectivity.
    
    Supports:
      - union(u, v): Merge components containing u and v
      - find(u): Find the representative of u's component
      - connected(u, v): Check if u and v are in the same component
    
    Using path compression and union by rank for near O(1) operations.
    """
    def __init__(self, vertices):
        self.parent = {v: v for v in vertices}
        self.rank = {v: 0 for v in vertices}
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # Path compression
        return self.parent[x]
    
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False  # Already in same component
        
        # Union by rank
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True
    
    def connected(self, x, y):
        return self.find(x) == self.find(y)
    
    def get_components(self):
        components = {}
        for v in self.parent:
            root = self.find(v)
            if root not in components:
                components[root] = set()
            components[root].add(v)
        return list(components.values())
 
 
# Example usage
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'C'],
    'C': ['A', 'B'],
    'D': ['E'],
    'E': ['D'],
    'F': []  # Isolated vertex
}
 
components = find_connected_components_bfs(graph)
print(f"Number of components: {len(components)}")
print("Components:", components)
# Output: 3 components: {'A', 'B', 'C'}, {'D', 'E'}, {'F'}
 
print(f"Is connected: {is_connected(graph)}")  # False
 
# Union-Find approach
uf = UnionFind(['A', 'B', 'C', 'D', 'E', 'F'])
for u, neighbors in graph.items():
    for v in neighbors:
        uf.union(u, v)
 
print("Components via Union-Find:", uf.get_components())
print(f"A and C connected: {uf.connected('A', 'C')}")  # True
print(f"A and D connected: {uf.connected('A', 'D')}")  # False

Bridges and Articulation Points

Bridge (Cut Edge):

Bridges are single points of failure. In a network, a bridge represents a link with no backup—if it fails, communication between some nodes becomes impossible.

Articulation Point (Cut Vertex):

An articulation point is a vertex whose removal (along with its incident edges) increases the number of connected components. Removing this vertex disconnects the graph.

Articulation points are critical nodes—servers, routers, or people whose removal would fragment the network.

Network Vulnerability

Finding Bridges and Articulation Points:

Tarjan's algorithm finds all bridges and articulation points in O(V + E) time using a single DFS. The key insight is tracking discovery times and low-link values:

Discovery time disc[v]: When vertex v was first visited during DFS
Low-link value low[v]: The minimum discovery time reachable from the subtree rooted at v

Articulation Point Detection: A vertex u is an articulation point if:

u is the DFS root and has two or more children, OR
u is not the root and has a child v where low[v] ≥ disc[u]

bridges_articulation.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
from typing import Dict, List, Set, Tuple
 
def find_bridges_and_articulation_points(
    graph: Dict[str, List[str]]
) -> Tuple[List[Tuple[str, str]], Set[str]]:
    """
    Find all bridges and articulation points using Tarjan's algorithm.
    
    Args:
        graph: Adjacency list of an undirected graph
    
    Returns:
        Tuple of (bridges, articulation_points)
    
    Time Complexity: O(V + E)
    Space Complexity: O(V)
    """
    disc = {}  # Discovery time of each vertex
    low = {}   # Lowest discovery time reachable
    parent = {}  # Parent in DFS tree
    bridges = []
    articulation_points = set()
    timer = [0]  # Using list for mutability in nested function
    
    def dfs(u):
        disc[u] = low[u] = timer[0]
        timer[0] += 1
        children = 0
        
        for v in graph.get(u, []):
            if v not in disc:  # Tree edge
                children += 1
                parent[v] = u
                dfs(v)
                
                # Update low value
                low[u] = min(low[u], low[v])
                
                # Bridge check: v cannot reach anything before u
                if low[v] > disc[u]:
                    bridges.append((u, v))
                
                # Articulation point check (non-root)
                if parent.get(u) is not None and low[v] >= disc[u]:
                    articulation_points.add(u)
                    
            elif v != parent.get(u):  # Back edge (not to parent)
                low[u] = min(low[u], disc[v])
        
        # Root is articulation point if it has 2+ children
        if parent.get(u) is None and children > 1:
            articulation_points.add(u)
    
    # Handle disconnected graphs
    for vertex in graph:
        if vertex not in disc:
            parent[vertex] = None
            dfs(vertex)
    
    return bridges, articulation_points
 
 
# Example: Graph with clear structure
#     A
#    / \
#   B - C - D - E
#           |   |
#           F - G
#
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'C'],
    'C': ['A', 'B', 'D'],
    'D': ['C', 'E', 'F'],
    'E': ['D', 'G'],
    'F': ['D', 'G'],
    'G': ['E', 'F']
}
 
bridges, articulation_points = find_bridges_and_articulation_points(graph)
 
print("Bridges (critical edges):", bridges)
# Output: [('C', 'D')] - removing C-D disconnects {A,B,C} from {D,E,F,G}
 
print("Articulation Points (critical vertices):", articulation_points)
# Output: {'C', 'D'} - removing C or D disconnects the graph
 
# A more vulnerable graph
linear_graph = {
    'A': ['B'],
    'B': ['A', 'C'],
    'C': ['B', 'D'],
    'D': ['C']
}
 
bridges, aps = find_bridges_and_articulation_points(linear_graph)
print("\nLinear graph bridges:", bridges)  # All edges are bridges
print("Linear graph articulation points:", aps)  # B and C

Special Types of Undirected Graphs

Several important families of undirected graphs have special properties that enable efficient algorithms or arise frequently in applications:

Complete Graph (K_n):

Cycle Graph (C_n):

A cycle graph is a single cycle of n vertices. Each vertex has exactly degree 2. It's the simplest connected graph with no leaves.

Path Graph (P_n):

A path graph is a simple path of n vertices. Two endpoints have degree 1; all internal vertices have degree 2. It's the simplest connected graph structure.

Structural Graph Types

•Tree: Connected graph with no cycles. |E| = |V| - 1. Unique path between every pair.
•Forest: Disjoint union of trees. An acyclic graph (may be disconnected).
•Bipartite Graph: Vertices partition into two sets; edges only between sets, never within.
•Complete Bipartite (K_m,n): Bipartite with all possible edges between the two sets.
•Star Graph: One central vertex connected to all others (K_1,n).

Density-Based Types

•Sparse Graph: |E| = O(|V|). Most real-world networks are sparse.
•Dense Graph: |E| = Θ(|V|²). Approaches complete graph density.
•Planar Graph: Can be drawn on a plane with no edge crossings. By Euler: |E| ≤ 3|V| - 6.
•Regular Graph: Every vertex has the same degree k (called k-regular).
•Random Graph G(n,p): n vertices; each edge included independently with probability p.

Trees Are Special

Summary: Undirected Graphs

We've explored undirected graphs comprehensively—from their formal definition to practical algorithms and real-world applications. Let's consolidate the key concepts:

Key Takeaways

•Undirected graphs model symmetric relationships — Edge {u, v} means u connects to v AND v connects to u. The relationship is mutual and bidirectional.
•Single degree concept — Unlike directed graphs, undirected graphs have one degree per vertex, counting all incident edges. The Handshaking Lemma states Σdeg(v) = 2|E|.
•Connectivity is simpler — If you can reach v from u, you can reach u from v. No need for 'strongly' vs 'weakly' connected distinctions.
•Connected components partition vertices — Every vertex belongs to exactly one component. BFS/DFS or Union-Find efficiently finds components.
•Bridges and articulation points — Critical edges/vertices whose removal disconnects the graph. Tarjan's algorithm finds them in O(V + E).
•Special graph types — Trees, complete graphs, bipartite graphs, planar graphs—each with unique properties enabling specialized algorithms.

What's Next:

Page Complete