Lesson 11

The following code visualizes the proof and shows that \(|V|-|E|\) indeed decreases faster than the number of connected components. As always, it is a good idea to play around with this interactive example: change the graph and see what happens.

from networkx import Graph, number_connected_components

nodes = [1, 2, 3, 4, 5, 6]
edges = [
    (1, 5), (4, 6), (5, 2), (2, 1), (3, 4), (6, 3),
    (1, 4), (3, 1), (2, 3)
]

graph = Graph()
graph.add_nodes_from(nodes)
for edge in edges:
    graph.add_edge(*edge)
    print(f'|V|-|E|={graph.number_of_nodes() - graph.number_of_edges()}, '
          f'c={number_connected_components(graph)}')

|V|-|E|=5, c=5
|V|-|E|=4, c=4
|V|-|E|=3, c=3
|V|-|E|=2, c=3
|V|-|E|=1, c=2
|V|-|E|=0, c=2
|V|-|E|=-1, c=1
|V|-|E|=-2, c=1
|V|-|E|=-3, c=1