Graph Properties - Learning Module

Loading content...

0/276

Complete Graphs and Subgraphs

The Extremes of Connectivity

What happens when a graph achieves maximum connectivity—when every vertex connects to every other? This extreme case, called a complete graph, serves as both a theoretical benchmark and a practical model for fully-connected systems.

Equally important is the concept of subgraphs—extracting meaningful portions from larger graphs. When analyzing a massive social network, we often focus on specific communities. When debugging a dependency graph, we might isolate a problematic subset. Subgraphs let us:

Decompose complex problems into manageable pieces
Identify dense regions (cliques) that indicate strong relationships
Focus analysis on relevant portions of large graphs
Prove properties using smaller examples

What You Will Learn

By the end of this page, you will understand complete graphs and their properties, master the distinction between subgraphs and induced subgraphs, learn about cliques and independent sets, explore bipartite graphs and graph coloring, and understand graph complements. These concepts form the foundation for advanced graph analysis and algorithm design.

Complete Graphs: Maximum Connectivity

A complete graph is a simple undirected graph where every pair of distinct vertices is connected by exactly one edge. This represents the maximum possible connectivity for a given number of vertices.

Notation and Definition

The complete graph on n vertices is denoted Kₙ (K for 'komplett' from German, or 'complete').

Kₙ = (V, E) where V = {1, 2, ..., n} and E = {{u, v} : u, v ∈ V, u ≠ v}

Key Properties of Kₙ:

Vertices: n
Edges: n(n-1)/2 (every pair connected)
Degree of each vertex: n-1 (connected to all others)
Regular: Kₙ is (n-1)-regular
Diameter: 1 (every vertex reachable in one step)
Connected: Yes, for n ≥ 1
Complete graphs are unique: There's only one Kₙ up to isomorphism

Converting Mermaid diagram...

Complete Graph Properties by Size
Graph	Vertices	Edges	Degree	Triangles
K₁	1	0	0	0
K₂	2	1	1	0
K₃	3	3	2	1
K₄	4	6	3	4
K₅	5	10	4	10
K₆	6	15	5	20
Kₙ	n	n(n-1)/2	n-1	C(n,3)

Edge Count Derivation

Why n(n-1)/2 edges? Each of n vertices connects to n-1 others. That's n(n-1) connections, but we've counted each edge twice (once from each endpoint). So:

|E| = n(n-1)/2

This is also C(n, 2), the number of ways to choose 2 vertices from n to form an edge.

Triangle Count

The number of triangles (K₃ subgraphs) in Kₙ is C(n, 3) = n(n-1)(n-2)/6. Each choice of 3 vertices forms exactly one triangle since they're all connected.

Complete Directed Graphs

In directed graphs, a complete graph has both edges (u→v and v→u) for every pair of distinct vertices. For n vertices, this gives n(n-1) directed edges. If we only have one edge per pair (tournament), we get n(n-1)/2 edges.

Subgraphs: Extracting Portions of Graphs

A subgraph is a graph formed from a subset of the vertices and edges of another graph. Understanding different types of subgraphs is essential for graph analysis and algorithm design.

Subgraph (General)

Graph H = (V', E') is a subgraph of G = (V, E) if:

V' ⊆ V (vertices of H are a subset of vertices of G)
E' ⊆ E (edges of H are a subset of edges of G)
Every edge in E' has both endpoints in V' (edges must connect existing vertices)

Spanning Subgraph

A spanning subgraph contains all vertices but possibly fewer edges:

V' = V (same vertices)
E' ⊆ E (subset of edges)

Example: A spanning tree of a connected graph uses all vertices but only n-1 edges.

Induced Subgraph (Most Important!)

An induced subgraph is determined entirely by choosing vertices; it includes all edges between those vertices:

V' ⊆ V (choose some vertices)
E' = {(u,v) ∈ E : u, v ∈ V'} (automatically include all edges between chosen vertices)

The induced subgraph on vertex set S is denoted G[S].

Subgraph (non-induced)

We can choose to keep or remove any edge between selected vertices.

Example: From K₄, select vertices {1,2,3} and edges {(1,2), (2,3)} only.

Result: A path, not a triangle.

Induced Subgraph

All edges between selected vertices are automatically included.

Example: From K₄, select vertices {1,2,3}.

Result: K₃ (triangle), because all three edges must be included.

subgraph_operations.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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
def create_subgraph(
    graph: dict[int, list[int]], 
    vertices: set[int], 
    edges: set[tuple[int, int]] | None = None
) -> dict[int, list[int]]:
    """
    Create a subgraph with specified vertices and edges.
    
    Args:
        graph: Original graph as adjacency list
        vertices: Subset of vertices to include
        edges: Optional set of edges to include. If None, include all edges
               between selected vertices (induced subgraph).
    
    Returns:
        Adjacency list for the subgraph
    """
    subgraph = {v: [] for v in vertices}
    
    for v in vertices:
        for neighbor in graph.get(v, []):
            if neighbor in vertices:
                if edges is None:
                    # Induced subgraph: include all edges between selected vertices
                    subgraph[v].append(neighbor)
                elif (v, neighbor) in edges or (neighbor, v) in edges:
                    # Explicit subgraph: only include specified edges
                    subgraph[v].append(neighbor)
    
    return subgraph
 
 
def induced_subgraph(
    graph: dict[int, list[int]], 
    vertices: set[int]
) -> dict[int, list[int]]:
    """
    Create the induced subgraph G[S] for vertex set S.
    
    The induced subgraph contains exactly the vertices in S
    and ALL edges between them that exist in G.
    
    Time Complexity: O(|S| * max_degree)
    """
    return create_subgraph(graph, vertices, edges=None)
 
 
def is_subgraph(H: dict[int, list[int]], G: dict[int, list[int]]) -> bool:
    """
    Check if H is a subgraph of G.
    
    H is a subgraph of G if:
    - Every vertex in H is in G
    - Every edge in H is in G
    """
    # Check vertices
    if not set(H.keys()).issubset(set(G.keys())):
        return False
    
    # Check edges
    for v in H:
        for neighbor in H[v]:
            if neighbor not in G.get(v, []):
                return False
    
    return True
 
 
# Example: Work with K4
k4 = {
    0: [1, 2, 3],
    1: [0, 2, 3],
    2: [0, 1, 3],
    3: [0, 1, 2],
}
 
# Induced subgraph on {0, 1, 2} = K3
k3 = induced_subgraph(k4, {0, 1, 2})
print(f"K3 from K4: {k3}")  # {0: [1, 2], 1: [0, 2], 2: [0, 1]}
 
# Non-induced subgraph: just a path
path = create_subgraph(k4, {0, 1, 2}, edges={(0, 1), (1, 2)})
print(f"Path: {path}")  # {0: [1], 1: [0, 2], 2: [1]}
 
# Spanning subgraph: spanning tree of K4
tree_edges = {(0, 1), (0, 2), (0, 3)}
spanning_tree = create_subgraph(k4, set(k4.keys()), tree_edges)
print(f"Spanning tree: {spanning_tree}")

Cliques: Complete Subgraphs

A clique is a subset of vertices that form a complete subgraph—every vertex in the clique is connected to every other vertex in the clique.

Formal Definition

A clique in graph G = (V, E) is a subset C ⊆ V such that:

Every pair of distinct vertices in C is connected by an edge
Equivalently, the induced subgraph G[C] is complete (isomorphic to K|C|)

Clique Terminology

k-clique: A clique of size k (forms Kₖ)
Maximal clique: A clique that cannot be extended by adding another vertex
Maximum clique: A clique of largest size in the graph
Clique number ω(G): The size of the maximum clique

Converting Mermaid diagram...

The graph above has:

3-clique (triangle): {1, 2, 3} shown in green
4-clique: {4, 5, 6, 7} shown in blue (if all edges exist)
Maximum clique has ω(G) = 4 (assuming the blue vertices form K₄)

Computational Complexity

Finding the maximum clique is NP-complete! This is one of the original 21 problems Richard Karp proved NP-complete in 1972.

Implications:

No known polynomial-time algorithm
For small graphs: exponential-time exact algorithms (e.g., Bron-Kerbosch)
For large graphs: approximation algorithms or heuristics
Checking if a given set is a clique is easy: O(k²) where k is set size

clique_operations.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
def is_clique(graph: dict[int, list[int]], vertices: set[int]) -> bool:
    """
    Check if a set of vertices forms a clique.
    
    Time Complexity: O(k²) where k = |vertices|
    """
    vertex_list = list(vertices)
    for i in range(len(vertex_list)):
        for j in range(i + 1, len(vertex_list)):
            u, v = vertex_list[i], vertex_list[j]
            if v not in graph.get(u, []):
                return False
    return True
 
 
def find_all_maximal_cliques(graph: dict[int, list[int]]) -> list[set[int]]:
    """
    Find all maximal cliques using the Bron-Kerbosch algorithm.
    
    A maximal clique cannot be extended by adding another vertex.
    
    Time Complexity: O(3^(n/3)) worst case (exponential)
    """
    cliques = []
    vertices = set(graph.keys())
    
    def bron_kerbosch(R: set, P: set, X: set):
        """
        R: Current clique being built
        P: Prospective vertices that could extend the clique
        X: Excluded vertices (already processed)
        """
        if not P and not X:
            # R is a maximal clique
            cliques.append(R.copy())
            return
        
        # Pivot optimization: choose vertex with most neighbors in P
        pivot = max(P | X, key=lambda v: len(set(graph.get(v, [])) & P), default=None)
        if pivot is None:
            return
        
        pivot_neighbors = set(graph.get(pivot, []))
        
        # Only consider vertices not adjacent to pivot
        for v in P - pivot_neighbors:
            neighbors = set(graph.get(v, []))
            bron_kerbosch(
                R | {v},
                P & neighbors,
                X & neighbors
            )
            P = P - {v}
            X = X | {v}
    
    bron_kerbosch(set(), vertices, set())
    return cliques
 
 
def maximum_clique(graph: dict[int, list[int]]) -> set[int]:
    """Find the maximum (largest) clique."""
    cliques = find_all_maximal_cliques(graph)
    return max(cliques, key=len) if cliques else set()
 
 
# Example
graph = {
    0: [1, 2],
    1: [0, 2, 3],
    2: [0, 1, 3],
    3: [1, 2, 4],
    4: [3]
}
 
print(f"Is {{0,1,2}} a clique? {is_clique(graph, {0, 1, 2})}")  # True
print(f"Is {{1,2,3}} a clique? {is_clique(graph, {1, 2, 3})}")  # True
print(f"Is {{0,1,2,3}} a clique? {is_clique(graph, {0, 1, 2, 3})}")  # False (0-3 not connected)
 
all_cliques = find_all_maximal_cliques(graph)
print(f"Maximal cliques: {all_cliques}")
print(f"Maximum clique: {maximum_clique(graph)}")

Real-World Clique Applications

Cliques appear in: (1) Social networks: friend groups where everyone knows everyone, (2) Bioinformatics: protein complexes where all proteins interact, (3) Marketing: customer segments with similar purchasing patterns, (4) Scheduling: time slots where all participants are available.

Independent Sets: The Opposite of Cliques

An independent set (also called a stable set) is the opposite of a clique—a set of vertices where no two are connected.

Formal Definition

An independent set in graph G = (V, E) is a subset I ⊆ V such that:

No pair of vertices in I is connected by an edge
Equivalently, the induced subgraph G[I] has no edges

Terminology

k-independent set: An independent set of size k
Maximal independent set: Cannot add another vertex without creating an edge
Maximum independent set: Largest independent set in the graph
Independence number α(G): Size of maximum independent set

Duality with Cliques

There's a beautiful duality between cliques and independent sets through graph complements (discussed later):

A clique in G corresponds to an independent set in the complement Ḡ, and vice versa.

Cliques vs Independent Sets
Property	Clique	Independent Set
Definition	All pairs connected	No pairs connected
Induced subgraph	Complete graph Kₖ	Empty graph (no edges)
Symbol for maximum	ω(G)	α(G)
Finding maximum	NP-complete	NP-complete
Verification	O(k²)	O(k²)
In complement graph	Becomes independent set	Becomes clique

independent_set.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
def is_independent_set(graph: dict[int, list[int]], vertices: set[int]) -> bool:
    """
    Check if a set of vertices forms an independent set (no edges between them).
    
    Time Complexity: O(k * max_degree) where k = |vertices|
    """
    for v in vertices:
        for neighbor in graph.get(v, []):
            if neighbor in vertices:
                return False  # Found an edge within the set
    return True
 
 
def greedy_maximal_independent_set(graph: dict[int, list[int]]) -> set[int]:
    """
    Find a maximal independent set using a greedy approach.
    
    Not guaranteed to find maximum, but runs in polynomial time.
    
    Time Complexity: O(V + E)
    """
    independent = set()
    excluded = set()
    
    # Process vertices in some order (degree-based heuristic often helps)
    vertices = sorted(graph.keys(), key=lambda v: len(graph.get(v, [])))
    
    for v in vertices:
        if v not in excluded:
            # Add v to independent set
            independent.add(v)
            # Exclude all neighbors (they can't be in the set now)
            for neighbor in graph.get(v, []):
                excluded.add(neighbor)
    
    return independent
 
 
def find_all_maximal_independent_sets(graph: dict[int, list[int]]) -> list[set[int]]:
    """
    Find all maximal independent sets.
    Uses complement graph + Bron-Kerbosch (cliques in complement = indep sets in original).
    """
    # Build complement graph
    all_vertices = set(graph.keys())
    complement = {v: list(all_vertices - {v} - set(graph.get(v, []))) for v in graph}
    
    # Find cliques in complement (they're independent sets in original)
    from typing import List
    independent_sets: List[set] = []
    
    def bron_kerbosch(R: set, P: set, X: set):
        if not P and not X:
            independent_sets.append(R.copy())
            return
        
        for v in list(P):
            neighbors = set(complement.get(v, []))
            bron_kerbosch(R | {v}, P & neighbors, X & neighbors)
            P = P - {v}
            X = X | {v}
    
    bron_kerbosch(set(), all_vertices, set())
    return independent_sets
 
 
# Example: Star graph (center + leaves)
star = {
    0: [1, 2, 3, 4],  # Center
    1: [0],           # Leaf
    2: [0],
    3: [0],
    4: [0],
}
 
# The leaves {1, 2, 3, 4} form an independent set
print(f"Is {{1,2,3,4}} independent? {is_independent_set(star, {1,2,3,4})}")  # True
print(f"Is {{0,1}} independent? {is_independent_set(star, {0,1})}")  # False
 
# Maximum independent set in star = all leaves
print(f"Greedy MIS: {greedy_maximal_independent_set(star)}")  # {1,2,3,4} or similar

Bipartite Graphs: Two-Party Structure

A bipartite graph is a graph whose vertices can be partitioned into two disjoint sets such that every edge connects a vertex in one set to a vertex in the other. There are no edges within either set.

Formal Definition

Graph G = (V, E) is bipartite if there exist sets U and W such that:

U ∪ W = V (they cover all vertices)
U ∩ W = ∅ (they're disjoint)
Every edge (u, v) ∈ E has one endpoint in U and one in W

Equivalent Characterization

A graph is bipartite if and only if it contains no odd-length cycles.

This provides both a definition and a test for bipartiteness.

Complete Bipartite Graphs

The complete bipartite graph Km,n has:

Two vertex sets of sizes m and n
Every vertex in the first set connected to every vertex in the second
Total edges: m × n

Converting Mermaid diagram...

bipartite_check.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
from collections import deque
 
def is_bipartite(graph: dict[int, list[int]]) -> tuple[bool, dict[int, int] | None]:
    """
    Check if a graph is bipartite using BFS 2-coloring.
    
    Returns:
        (is_bipartite, coloring)
        - is_bipartite: True if graph is bipartite
        - coloring: dict mapping vertex -> 0 or 1 (its partition), or None if not bipartite
        
    Time Complexity: O(V + E)
    """
    color = {}
    
    for start in graph:
        if start in color:
            continue  # Already colored (connected component already processed)
        
        # BFS to 2-color this component
        queue = deque([start])
        color[start] = 0
        
        while queue:
            vertex = queue.popleft()
            current_color = color[vertex]
            next_color = 1 - current_color  # Alternate: 0->1, 1->0
            
            for neighbor in graph.get(vertex, []):
                if neighbor not in color:
                    color[neighbor] = next_color
                    queue.append(neighbor)
                elif color[neighbor] == current_color:
                    # Same color = odd cycle = not bipartite
                    return False, None
    
    return True, color
 
 
def get_bipartition(graph: dict[int, list[int]]) -> tuple[set[int], set[int]] | None:
    """
    Get the two vertex sets of a bipartite graph.
    
    Returns (set_0, set_1) or None if not bipartite.
    """
    is_bip, coloring = is_bipartite(graph)
    if not is_bip:
        return None
    
    set_0 = {v for v, c in coloring.items() if c == 0}
    set_1 = {v for v, c in coloring.items() if c == 1}
    return set_0, set_1
 
 
# Examples
bipartite = {
    0: [2, 3],  # Set A: {0, 1}
    1: [2, 3],  # Set B: {2, 3}
    2: [0, 1],
    3: [0, 1],
}
 
triangle = {
    0: [1, 2],
    1: [0, 2],
    2: [0, 1],
}
 
is_bip, coloring = is_bipartite(bipartite)
print(f"Bipartite? {is_bip}, partition: {get_bipartition(bipartite)}")  # True
 
is_bip, _ = is_bipartite(triangle)
print(f"Triangle bipartite? {is_bip}")  # False (odd cycle)

Bipartite Applications

Bipartite structure appears in: matching problems (job applicants ↔ jobs), recommendation systems (users ↔ items), constraint satisfaction (variables ↔ clauses), and network flow (sources ↔ sinks). Recognizing bipartiteness enables specialized algorithms like Hopcroft-Karp for maximum matching.

Graph Complement: The Inverse of Connectivity

The complement of a graph G, denoted Ḡ or G', has the same vertices but opposite edges—an edge exists in Ḡ if and only if it doesn't exist in G (for distinct vertex pairs).

Formal Definition

For graph G = (V, E), its complement is Ḡ = (V, Ē) where:

Ē = {(u, v) : u, v ∈ V, u ≠ v, (u, v) ∉ E}

Properties

Edge count: |E(Ḡ)| = n(n-1)/2 - |E(G)| = |E(Kₙ)| - |E(G)|
Self-inverse: The complement of the complement is the original: Ḡ̄ = G
Kₙ complement: K̄ₙ has no edges (empty graph)
Empty graph complement: Complement of empty graph is Kₙ
Sum: E(G) ∪ E(Ḡ) = E(Kₙ) and E(G) ∩ E(Ḡ) = ∅

graph_complement.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
def complement(graph: dict[int, list[int]]) -> dict[int, list[int]]:
    """
    Compute the complement of an undirected simple graph.
    
    The complement has an edge between u and v IFF
    the original graph does NOT have that edge.
    
    Time Complexity: O(V²)
    Space Complexity: O(V²) for dense complement
    """
    vertices = set(graph.keys())
    comp = {v: [] for v in vertices}
    
    for u in vertices:
        neighbors_of_u = set(graph.get(u, []))
        for v in vertices:
            if v != u and v not in neighbors_of_u:
                comp[u].append(v)
    
    return comp
 
 
def is_self_complementary(graph: dict[int, list[int]]) -> bool:
    """
    Check if a graph is isomorphic to its complement.
    (Simplified check: same edge count, same degree sequence)
    """
    comp = complement(graph)
    
    # Quick check: must have same number of edges
    edges_original = sum(len(adj) for adj in graph.values()) // 2
    edges_comp = sum(len(adj) for adj in comp.values()) // 2
    
    if edges_original != edges_comp:
        return False
    
    # Check degree sequences match
    degrees_original = sorted(len(adj) for adj in graph.values())
    degrees_comp = sorted(len(adj) for adj in comp.values())
    
    return degrees_original == degrees_comp
 
 
# Example: Path graph P4
p4 = {
    0: [1],
    1: [0, 2],
    2: [1, 3],
    3: [2],
}
# Original: 0-1-2-3 (path)
# Complement: 0-2, 0-3, 1-3 (forms a different shape)
 
comp_p4 = complement(p4)
print(f"P4: {p4}")
print(f"Complement: {comp_p4}")
 
# P4 is actually self-complementary!
print(f"P4 self-complementary? {is_self_complementary(p4)}")
 
 
# Duality example
def clique_via_complement(graph: dict[int, list[int]], vertices: set[int]) -> bool:
    """A set is a clique in G iff it's an independent set in complement(G)."""
    comp = complement(graph)
    # Check if vertices form independent set in complement
    for v in vertices:
        for neighbor in comp.get(v, []):
            if neighbor in vertices:
                return False  # Has edge in complement = not clique in original
    return True

Self-Complementary Graphs

Some graphs are self-complementary: isomorphic to their own complement. Examples include P₄ (4-vertex path) and C₅ (5-cycle). Self-complementary graphs on n vertices exist only when n(n-1)/2 is even, meaning n ≡ 0 or 1 (mod 4).

Graph Coloring: Partitioning into Independent Sets

Graph coloring assigns colors to vertices such that no two adjacent vertices share the same color. Each color class forms an independent set.

Definitions

k-coloring: An assignment of k colors to vertices with no adjacent same-color pairs
k-colorable: A graph that admits a k-coloring
Chromatic number χ(G): The minimum k such that G is k-colorable

Key Results

Every graph is n-colorable (give each vertex its own color)
Bipartite graphs are exactly the 2-colorable graphs
Complete graph Kₙ has χ(Kₙ) = n (all vertices adjacent, all need different colors)
χ(G) ≥ ω(G): Chromatic number is at least the clique number (clique vertices all need different colors)
Four Color Theorem: Every planar graph is 4-colorable

graph_coloring.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
def greedy_coloring(graph: dict[int, list[int]]) -> dict[int, int]:
    """
    Greedy graph coloring algorithm.
    
    Assigns the smallest possible color to each vertex in order.
    Not optimal, but provides upper bound on chromatic number.
    
    Time Complexity: O(V + E)
    """
    color = {}
    
    for vertex in graph:
        # Find colors used by neighbors
        neighbor_colors = {color[n] for n in graph.get(vertex, []) if n in color}
        
        # Assign smallest color not used by neighbors
        c = 0
        while c in neighbor_colors:
            c += 1
        color[vertex] = c
    
    return color
 
 
def chromatic_number_upper_bound(graph: dict[int, list[int]]) -> int:
    """Upper bound on chromatic number from greedy coloring."""
    coloring = greedy_coloring(graph)
    return max(coloring.values()) + 1 if coloring else 0
 
 
def is_k_colorable(graph: dict[int, list[int]], k: int) -> tuple[bool, dict | None]:
    """
    Check if graph is k-colorable using backtracking.
    
    Returns (is_colorable, coloring or None)
    """
    vertices = list(graph.keys())
    color = {}
    
    def backtrack(idx: int) -> bool:
        if idx == len(vertices):
            return True  # All vertices colored successfully
        
        vertex = vertices[idx]
        neighbor_colors = {color.get(n) for n in graph.get(vertex, []) if n in color}
        
        for c in range(k):
            if c not in neighbor_colors:
                color[vertex] = c
                if backtrack(idx + 1):
                    return True
                del color[vertex]
        
        return False
    
    if backtrack(0):
        return True, color
    return False, None
 
 
# Examples
petersen = {  # Petersen graph (simplified subset)
    0: [1, 4, 5], 1: [0, 2, 6], 2: [1, 3, 7],
    3: [2, 4, 8], 4: [0, 3, 9], 5: [0, 7, 8],
    6: [1, 8, 9], 7: [2, 5, 9], 8: [3, 5, 6], 9: [4, 6, 7]
}
 
coloring = greedy_coloring(petersen)
print(f"Greedy coloring uses {chromatic_number_upper_bound(petersen)} colors")
 
# Check if 3-colorable
is_3col, col3 = is_k_colorable(petersen, 3)
print(f"Petersen 3-colorable? {is_3col}")

Coloring Applications

Graph coloring solves: scheduling (time slots = colors, conflicts = edges), register allocation (variables = vertices, interference = edges), map coloring (regions = vertices, borders = edges), and frequency assignment (transmitters = vertices, interference = edges).

Summary: Complete Graphs and Subgraphs

Complete graphs represent maximum connectivity, while subgraphs let us extract and analyze portions of larger graphs. These concepts interweave with cliques, independent sets, bipartiteness, and coloring to form a rich theoretical foundation. Let's consolidate:

Key Takeaways

•Complete graph Kₙ has all possible edges: n(n-1)/2 edges, every vertex degree n-1
•Subgraphs are graphs formed from subsets of vertices and edges; induced subgraphs automatically include all edges between selected vertices
•Cliques are complete subgraphs; finding the maximum clique is NP-complete
•Independent sets have no internal edges; they are cliques in the complement graph
•Bipartite graphs partition into two sets with edges only between sets; equivalent to 2-colorability or no odd cycles
•Graph complement Ḡ has edges wherever G doesn't; cliques ↔ independent sets under complementation
•Graph coloring partitions vertices into independent sets; chromatic number χ(G) ≥ clique number ω(G)

Module Complete:

With this page, you've completed the Graph Properties module, covering connectivity, cycles, degrees, and special graph structures. You now have the vocabulary and analytical tools to describe and reason about graph structure—essential preparation for graph algorithms in the upcoming chapters.

Module Complete

You've mastered the fundamental structural properties of graphs: connectivity tells us what can reach what, cycles reveal circular dependencies, degrees quantify local connectivity, and complete subgraphs identify dense clusters. Next, we'll explore how trees relate to graphs, connecting these data structures in a unified framework.

Complete Graphs and Subgraphs

The Extremes of Connectivity

Decompose complex problems into manageable pieces
Identify dense regions (cliques) that indicate strong relationships
Focus analysis on relevant portions of large graphs
Prove properties using smaller examples

What You Will Learn

Complete Graphs: Maximum Connectivity

Notation and Definition

The complete graph on n vertices is denoted Kₙ (K for 'komplett' from German, or 'complete').

Kₙ = (V, E) where V = {1, 2, ..., n} and E = {{u, v} : u, v ∈ V, u ≠ v}

Key Properties of Kₙ:

Vertices: n
Edges: n(n-1)/2 (every pair connected)
Degree of each vertex: n-1 (connected to all others)
Regular: Kₙ is (n-1)-regular
Diameter: 1 (every vertex reachable in one step)
Connected: Yes, for n ≥ 1
Complete graphs are unique: There's only one Kₙ up to isomorphism

Converting Mermaid diagram...

Complete Graph Properties by Size
Graph	Vertices	Edges	Degree	Triangles
K₁	1	0	0	0
K₂	2	1	1	0
K₃	3	3	2	1
K₄	4	6	3	4
K₅	5	10	4	10
K₆	6	15	5	20
Kₙ	n	n(n-1)/2	n-1	C(n,3)

Edge Count Derivation

Why n(n-1)/2 edges? Each of n vertices connects to n-1 others. That's n(n-1) connections, but we've counted each edge twice (once from each endpoint). So:

|E| = n(n-1)/2

This is also C(n, 2), the number of ways to choose 2 vertices from n to form an edge.

Triangle Count

The number of triangles (K₃ subgraphs) in Kₙ is C(n, 3) = n(n-1)(n-2)/6. Each choice of 3 vertices forms exactly one triangle since they're all connected.

Complete Directed Graphs

Subgraphs: Extracting Portions of Graphs

A subgraph is a graph formed from a subset of the vertices and edges of another graph. Understanding different types of subgraphs is essential for graph analysis and algorithm design.

Subgraph (General)

Graph H = (V', E') is a subgraph of G = (V, E) if:

V' ⊆ V (vertices of H are a subset of vertices of G)
E' ⊆ E (edges of H are a subset of edges of G)
Every edge in E' has both endpoints in V' (edges must connect existing vertices)

Spanning Subgraph

A spanning subgraph contains all vertices but possibly fewer edges:

V' = V (same vertices)
E' ⊆ E (subset of edges)

Example: A spanning tree of a connected graph uses all vertices but only n-1 edges.

Induced Subgraph (Most Important!)

An induced subgraph is determined entirely by choosing vertices; it includes all edges between those vertices:

V' ⊆ V (choose some vertices)
E' = {(u,v) ∈ E : u, v ∈ V'} (automatically include all edges between chosen vertices)

The induced subgraph on vertex set S is denoted G[S].

Subgraph (non-induced)

We can choose to keep or remove any edge between selected vertices.

Example: From K₄, select vertices {1,2,3} and edges {(1,2), (2,3)} only.

Result: A path, not a triangle.

Induced Subgraph

All edges between selected vertices are automatically included.

Example: From K₄, select vertices {1,2,3}.

Result: K₃ (triangle), because all three edges must be included.

subgraph_operations.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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
def create_subgraph(
    graph: dict[int, list[int]], 
    vertices: set[int], 
    edges: set[tuple[int, int]] | None = None
) -> dict[int, list[int]]:
    """
    Create a subgraph with specified vertices and edges.
    
    Args:
        graph: Original graph as adjacency list
        vertices: Subset of vertices to include
        edges: Optional set of edges to include. If None, include all edges
               between selected vertices (induced subgraph).
    
    Returns:
        Adjacency list for the subgraph
    """
    subgraph = {v: [] for v in vertices}
    
    for v in vertices:
        for neighbor in graph.get(v, []):
            if neighbor in vertices:
                if edges is None:
                    # Induced subgraph: include all edges between selected vertices
                    subgraph[v].append(neighbor)
                elif (v, neighbor) in edges or (neighbor, v) in edges:
                    # Explicit subgraph: only include specified edges
                    subgraph[v].append(neighbor)
    
    return subgraph
 
 
def induced_subgraph(
    graph: dict[int, list[int]], 
    vertices: set[int]
) -> dict[int, list[int]]:
    """
    Create the induced subgraph G[S] for vertex set S.
    
    The induced subgraph contains exactly the vertices in S
    and ALL edges between them that exist in G.
    
    Time Complexity: O(|S| * max_degree)
    """
    return create_subgraph(graph, vertices, edges=None)
 
 
def is_subgraph(H: dict[int, list[int]], G: dict[int, list[int]]) -> bool:
    """
    Check if H is a subgraph of G.
    
    H is a subgraph of G if:
    - Every vertex in H is in G
    - Every edge in H is in G
    """
    # Check vertices
    if not set(H.keys()).issubset(set(G.keys())):
        return False
    
    # Check edges
    for v in H:
        for neighbor in H[v]:
            if neighbor not in G.get(v, []):
                return False
    
    return True
 
 
# Example: Work with K4
k4 = {
    0: [1, 2, 3],
    1: [0, 2, 3],
    2: [0, 1, 3],
    3: [0, 1, 2],
}
 
# Induced subgraph on {0, 1, 2} = K3
k3 = induced_subgraph(k4, {0, 1, 2})
print(f"K3 from K4: {k3}")  # {0: [1, 2], 1: [0, 2], 2: [0, 1]}
 
# Non-induced subgraph: just a path
path = create_subgraph(k4, {0, 1, 2}, edges={(0, 1), (1, 2)})
print(f"Path: {path}")  # {0: [1], 1: [0, 2], 2: [1]}
 
# Spanning subgraph: spanning tree of K4
tree_edges = {(0, 1), (0, 2), (0, 3)}
spanning_tree = create_subgraph(k4, set(k4.keys()), tree_edges)
print(f"Spanning tree: {spanning_tree}")

Cliques: Complete Subgraphs

A clique is a subset of vertices that form a complete subgraph—every vertex in the clique is connected to every other vertex in the clique.

Formal Definition

A clique in graph G = (V, E) is a subset C ⊆ V such that:

Every pair of distinct vertices in C is connected by an edge
Equivalently, the induced subgraph G[C] is complete (isomorphic to K|C|)

Clique Terminology

k-clique: A clique of size k (forms Kₖ)
Maximal clique: A clique that cannot be extended by adding another vertex
Maximum clique: A clique of largest size in the graph
Clique number ω(G): The size of the maximum clique

Converting Mermaid diagram...

The graph above has:

3-clique (triangle): {1, 2, 3} shown in green
4-clique: {4, 5, 6, 7} shown in blue (if all edges exist)
Maximum clique has ω(G) = 4 (assuming the blue vertices form K₄)

Computational Complexity

Finding the maximum clique is NP-complete! This is one of the original 21 problems Richard Karp proved NP-complete in 1972.

Implications:

No known polynomial-time algorithm
For small graphs: exponential-time exact algorithms (e.g., Bron-Kerbosch)
For large graphs: approximation algorithms or heuristics
Checking if a given set is a clique is easy: O(k²) where k is set size

clique_operations.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
def is_clique(graph: dict[int, list[int]], vertices: set[int]) -> bool:
    """
    Check if a set of vertices forms a clique.
    
    Time Complexity: O(k²) where k = |vertices|
    """
    vertex_list = list(vertices)
    for i in range(len(vertex_list)):
        for j in range(i + 1, len(vertex_list)):
            u, v = vertex_list[i], vertex_list[j]
            if v not in graph.get(u, []):
                return False
    return True
 
 
def find_all_maximal_cliques(graph: dict[int, list[int]]) -> list[set[int]]:
    """
    Find all maximal cliques using the Bron-Kerbosch algorithm.
    
    A maximal clique cannot be extended by adding another vertex.
    
    Time Complexity: O(3^(n/3)) worst case (exponential)
    """
    cliques = []
    vertices = set(graph.keys())
    
    def bron_kerbosch(R: set, P: set, X: set):
        """
        R: Current clique being built
        P: Prospective vertices that could extend the clique
        X: Excluded vertices (already processed)
        """
        if not P and not X:
            # R is a maximal clique
            cliques.append(R.copy())
            return
        
        # Pivot optimization: choose vertex with most neighbors in P
        pivot = max(P | X, key=lambda v: len(set(graph.get(v, [])) & P), default=None)
        if pivot is None:
            return
        
        pivot_neighbors = set(graph.get(pivot, []))
        
        # Only consider vertices not adjacent to pivot
        for v in P - pivot_neighbors:
            neighbors = set(graph.get(v, []))
            bron_kerbosch(
                R | {v},
                P & neighbors,
                X & neighbors
            )
            P = P - {v}
            X = X | {v}
    
    bron_kerbosch(set(), vertices, set())
    return cliques
 
 
def maximum_clique(graph: dict[int, list[int]]) -> set[int]:
    """Find the maximum (largest) clique."""
    cliques = find_all_maximal_cliques(graph)
    return max(cliques, key=len) if cliques else set()
 
 
# Example
graph = {
    0: [1, 2],
    1: [0, 2, 3],
    2: [0, 1, 3],
    3: [1, 2, 4],
    4: [3]
}
 
print(f"Is {{0,1,2}} a clique? {is_clique(graph, {0, 1, 2})}")  # True
print(f"Is {{1,2,3}} a clique? {is_clique(graph, {1, 2, 3})}")  # True
print(f"Is {{0,1,2,3}} a clique? {is_clique(graph, {0, 1, 2, 3})}")  # False (0-3 not connected)
 
all_cliques = find_all_maximal_cliques(graph)
print(f"Maximal cliques: {all_cliques}")
print(f"Maximum clique: {maximum_clique(graph)}")

Real-World Clique Applications

Independent Sets: The Opposite of Cliques

An independent set (also called a stable set) is the opposite of a clique—a set of vertices where no two are connected.

Formal Definition

An independent set in graph G = (V, E) is a subset I ⊆ V such that:

No pair of vertices in I is connected by an edge
Equivalently, the induced subgraph G[I] has no edges

Terminology

k-independent set: An independent set of size k
Maximal independent set: Cannot add another vertex without creating an edge
Maximum independent set: Largest independent set in the graph
Independence number α(G): Size of maximum independent set

Duality with Cliques

There's a beautiful duality between cliques and independent sets through graph complements (discussed later):

A clique in G corresponds to an independent set in the complement Ḡ, and vice versa.

Cliques vs Independent Sets
Property	Clique	Independent Set
Definition	All pairs connected	No pairs connected
Induced subgraph	Complete graph Kₖ	Empty graph (no edges)
Symbol for maximum	ω(G)	α(G)
Finding maximum	NP-complete	NP-complete
Verification	O(k²)	O(k²)
In complement graph	Becomes independent set	Becomes clique

independent_set.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
def is_independent_set(graph: dict[int, list[int]], vertices: set[int]) -> bool:
    """
    Check if a set of vertices forms an independent set (no edges between them).
    
    Time Complexity: O(k * max_degree) where k = |vertices|
    """
    for v in vertices:
        for neighbor in graph.get(v, []):
            if neighbor in vertices:
                return False  # Found an edge within the set
    return True
 
 
def greedy_maximal_independent_set(graph: dict[int, list[int]]) -> set[int]:
    """
    Find a maximal independent set using a greedy approach.
    
    Not guaranteed to find maximum, but runs in polynomial time.
    
    Time Complexity: O(V + E)
    """
    independent = set()
    excluded = set()
    
    # Process vertices in some order (degree-based heuristic often helps)
    vertices = sorted(graph.keys(), key=lambda v: len(graph.get(v, [])))
    
    for v in vertices:
        if v not in excluded:
            # Add v to independent set
            independent.add(v)
            # Exclude all neighbors (they can't be in the set now)
            for neighbor in graph.get(v, []):
                excluded.add(neighbor)
    
    return independent
 
 
def find_all_maximal_independent_sets(graph: dict[int, list[int]]) -> list[set[int]]:
    """
    Find all maximal independent sets.
    Uses complement graph + Bron-Kerbosch (cliques in complement = indep sets in original).
    """
    # Build complement graph
    all_vertices = set(graph.keys())
    complement = {v: list(all_vertices - {v} - set(graph.get(v, []))) for v in graph}
    
    # Find cliques in complement (they're independent sets in original)
    from typing import List
    independent_sets: List[set] = []
    
    def bron_kerbosch(R: set, P: set, X: set):
        if not P and not X:
            independent_sets.append(R.copy())
            return
        
        for v in list(P):
            neighbors = set(complement.get(v, []))
            bron_kerbosch(R | {v}, P & neighbors, X & neighbors)
            P = P - {v}
            X = X | {v}
    
    bron_kerbosch(set(), all_vertices, set())
    return independent_sets
 
 
# Example: Star graph (center + leaves)
star = {
    0: [1, 2, 3, 4],  # Center
    1: [0],           # Leaf
    2: [0],
    3: [0],
    4: [0],
}
 
# The leaves {1, 2, 3, 4} form an independent set
print(f"Is {{1,2,3,4}} independent? {is_independent_set(star, {1,2,3,4})}")  # True
print(f"Is {{0,1}} independent? {is_independent_set(star, {0,1})}")  # False
 
# Maximum independent set in star = all leaves
print(f"Greedy MIS: {greedy_maximal_independent_set(star)}")  # {1,2,3,4} or similar

Bipartite Graphs: Two-Party Structure

Formal Definition

Graph G = (V, E) is bipartite if there exist sets U and W such that:

U ∪ W = V (they cover all vertices)
U ∩ W = ∅ (they're disjoint)
Every edge (u, v) ∈ E has one endpoint in U and one in W

Equivalent Characterization

A graph is bipartite if and only if it contains no odd-length cycles.

This provides both a definition and a test for bipartiteness.

Complete Bipartite Graphs

The complete bipartite graph Km,n has:

Two vertex sets of sizes m and n
Every vertex in the first set connected to every vertex in the second
Total edges: m × n

Converting Mermaid diagram...

bipartite_check.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
from collections import deque
 
def is_bipartite(graph: dict[int, list[int]]) -> tuple[bool, dict[int, int] | None]:
    """
    Check if a graph is bipartite using BFS 2-coloring.
    
    Returns:
        (is_bipartite, coloring)
        - is_bipartite: True if graph is bipartite
        - coloring: dict mapping vertex -> 0 or 1 (its partition), or None if not bipartite
        
    Time Complexity: O(V + E)
    """
    color = {}
    
    for start in graph:
        if start in color:
            continue  # Already colored (connected component already processed)
        
        # BFS to 2-color this component
        queue = deque([start])
        color[start] = 0
        
        while queue:
            vertex = queue.popleft()
            current_color = color[vertex]
            next_color = 1 - current_color  # Alternate: 0->1, 1->0
            
            for neighbor in graph.get(vertex, []):
                if neighbor not in color:
                    color[neighbor] = next_color
                    queue.append(neighbor)
                elif color[neighbor] == current_color:
                    # Same color = odd cycle = not bipartite
                    return False, None
    
    return True, color
 
 
def get_bipartition(graph: dict[int, list[int]]) -> tuple[set[int], set[int]] | None:
    """
    Get the two vertex sets of a bipartite graph.
    
    Returns (set_0, set_1) or None if not bipartite.
    """
    is_bip, coloring = is_bipartite(graph)
    if not is_bip:
        return None
    
    set_0 = {v for v, c in coloring.items() if c == 0}
    set_1 = {v for v, c in coloring.items() if c == 1}
    return set_0, set_1
 
 
# Examples
bipartite = {
    0: [2, 3],  # Set A: {0, 1}
    1: [2, 3],  # Set B: {2, 3}
    2: [0, 1],
    3: [0, 1],
}
 
triangle = {
    0: [1, 2],
    1: [0, 2],
    2: [0, 1],
}
 
is_bip, coloring = is_bipartite(bipartite)
print(f"Bipartite? {is_bip}, partition: {get_bipartition(bipartite)}")  # True
 
is_bip, _ = is_bipartite(triangle)
print(f"Triangle bipartite? {is_bip}")  # False (odd cycle)

Bipartite Applications

Graph Complement: The Inverse of Connectivity

The complement of a graph G, denoted Ḡ or G', has the same vertices but opposite edges—an edge exists in Ḡ if and only if it doesn't exist in G (for distinct vertex pairs).

Formal Definition

For graph G = (V, E), its complement is Ḡ = (V, Ē) where:

Ē = {(u, v) : u, v ∈ V, u ≠ v, (u, v) ∉ E}

Properties

Edge count: |E(Ḡ)| = n(n-1)/2 - |E(G)| = |E(Kₙ)| - |E(G)|
Self-inverse: The complement of the complement is the original: Ḡ̄ = G
Kₙ complement: K̄ₙ has no edges (empty graph)
Empty graph complement: Complement of empty graph is Kₙ
Sum: E(G) ∪ E(Ḡ) = E(Kₙ) and E(G) ∩ E(Ḡ) = ∅

graph_complement.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
def complement(graph: dict[int, list[int]]) -> dict[int, list[int]]:
    """
    Compute the complement of an undirected simple graph.
    
    The complement has an edge between u and v IFF
    the original graph does NOT have that edge.
    
    Time Complexity: O(V²)
    Space Complexity: O(V²) for dense complement
    """
    vertices = set(graph.keys())
    comp = {v: [] for v in vertices}
    
    for u in vertices:
        neighbors_of_u = set(graph.get(u, []))
        for v in vertices:
            if v != u and v not in neighbors_of_u:
                comp[u].append(v)
    
    return comp
 
 
def is_self_complementary(graph: dict[int, list[int]]) -> bool:
    """
    Check if a graph is isomorphic to its complement.
    (Simplified check: same edge count, same degree sequence)
    """
    comp = complement(graph)
    
    # Quick check: must have same number of edges
    edges_original = sum(len(adj) for adj in graph.values()) // 2
    edges_comp = sum(len(adj) for adj in comp.values()) // 2
    
    if edges_original != edges_comp:
        return False
    
    # Check degree sequences match
    degrees_original = sorted(len(adj) for adj in graph.values())
    degrees_comp = sorted(len(adj) for adj in comp.values())
    
    return degrees_original == degrees_comp
 
 
# Example: Path graph P4
p4 = {
    0: [1],
    1: [0, 2],
    2: [1, 3],
    3: [2],
}
# Original: 0-1-2-3 (path)
# Complement: 0-2, 0-3, 1-3 (forms a different shape)
 
comp_p4 = complement(p4)
print(f"P4: {p4}")
print(f"Complement: {comp_p4}")
 
# P4 is actually self-complementary!
print(f"P4 self-complementary? {is_self_complementary(p4)}")
 
 
# Duality example
def clique_via_complement(graph: dict[int, list[int]], vertices: set[int]) -> bool:
    """A set is a clique in G iff it's an independent set in complement(G)."""
    comp = complement(graph)
    # Check if vertices form independent set in complement
    for v in vertices:
        for neighbor in comp.get(v, []):
            if neighbor in vertices:
                return False  # Has edge in complement = not clique in original
    return True

Self-Complementary Graphs

Graph Coloring: Partitioning into Independent Sets

Graph coloring assigns colors to vertices such that no two adjacent vertices share the same color. Each color class forms an independent set.

Definitions

k-coloring: An assignment of k colors to vertices with no adjacent same-color pairs
k-colorable: A graph that admits a k-coloring
Chromatic number χ(G): The minimum k such that G is k-colorable

Key Results

Every graph is n-colorable (give each vertex its own color)
Bipartite graphs are exactly the 2-colorable graphs
Complete graph Kₙ has χ(Kₙ) = n (all vertices adjacent, all need different colors)
χ(G) ≥ ω(G): Chromatic number is at least the clique number (clique vertices all need different colors)
Four Color Theorem: Every planar graph is 4-colorable

graph_coloring.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
def greedy_coloring(graph: dict[int, list[int]]) -> dict[int, int]:
    """
    Greedy graph coloring algorithm.
    
    Assigns the smallest possible color to each vertex in order.
    Not optimal, but provides upper bound on chromatic number.
    
    Time Complexity: O(V + E)
    """
    color = {}
    
    for vertex in graph:
        # Find colors used by neighbors
        neighbor_colors = {color[n] for n in graph.get(vertex, []) if n in color}
        
        # Assign smallest color not used by neighbors
        c = 0
        while c in neighbor_colors:
            c += 1
        color[vertex] = c
    
    return color
 
 
def chromatic_number_upper_bound(graph: dict[int, list[int]]) -> int:
    """Upper bound on chromatic number from greedy coloring."""
    coloring = greedy_coloring(graph)
    return max(coloring.values()) + 1 if coloring else 0
 
 
def is_k_colorable(graph: dict[int, list[int]], k: int) -> tuple[bool, dict | None]:
    """
    Check if graph is k-colorable using backtracking.
    
    Returns (is_colorable, coloring or None)
    """
    vertices = list(graph.keys())
    color = {}
    
    def backtrack(idx: int) -> bool:
        if idx == len(vertices):
            return True  # All vertices colored successfully
        
        vertex = vertices[idx]
        neighbor_colors = {color.get(n) for n in graph.get(vertex, []) if n in color}
        
        for c in range(k):
            if c not in neighbor_colors:
                color[vertex] = c
                if backtrack(idx + 1):
                    return True
                del color[vertex]
        
        return False
    
    if backtrack(0):
        return True, color
    return False, None
 
 
# Examples
petersen = {  # Petersen graph (simplified subset)
    0: [1, 4, 5], 1: [0, 2, 6], 2: [1, 3, 7],
    3: [2, 4, 8], 4: [0, 3, 9], 5: [0, 7, 8],
    6: [1, 8, 9], 7: [2, 5, 9], 8: [3, 5, 6], 9: [4, 6, 7]
}
 
coloring = greedy_coloring(petersen)
print(f"Greedy coloring uses {chromatic_number_upper_bound(petersen)} colors")
 
# Check if 3-colorable
is_3col, col3 = is_k_colorable(petersen, 3)
print(f"Petersen 3-colorable? {is_3col}")

Coloring Applications

Summary: Complete Graphs and Subgraphs

Key Takeaways

•Complete graph Kₙ has all possible edges: n(n-1)/2 edges, every vertex degree n-1
•Subgraphs are graphs formed from subsets of vertices and edges; induced subgraphs automatically include all edges between selected vertices
•Cliques are complete subgraphs; finding the maximum clique is NP-complete
•Independent sets have no internal edges; they are cliques in the complement graph
•Bipartite graphs partition into two sets with edges only between sets; equivalent to 2-colorability or no odd cycles
•Graph complement Ḡ has edges wherever G doesn't; cliques ↔ independent sets under complementation
•Graph coloring partitions vertices into independent sets; chromatic number χ(G) ≥ clique number ω(G)

Module Complete:

Module Complete