From charlesreid1


Finding Connected Components

To find all connected components on a graph, we have to consider directed and undirected components separately.

Undirected Graphs: Finding Connected Components

The result of finding connected components is a forest (a group of trees). To find the connected components, we perform a depth-first search, adding each discovered node to a dictionary. We want to iterate through every vertex on the graph. We perform a depth-first search on a random vertex. We then move on to the next vertex, and if it is not already a part of an existing forest, we perform another depth-first search on it.

This procedure will run in time, because even if we perform multiple depth-first searches, we are only performing it on separate trees.

// u is an empty dictionary
def dfs_connected(g):
    forest is empty dictionary
    for each vertex u in graph:
        if u not in forest:
            forest[u] = None
            do_dfs(g, u, forest)
    return forest

// complementary method: do depth first search
def do_dfs(g, u, discovered):
    for e in g.incident_edges(u):
        if v not in discovered:
            discovered[v] = e
            do_dfs(g, v, discovered)

Directed Graphs: Finding Strongly Connected Components

A strongly connected directed graph is one in which, for every pair of vertices u and v, u can be reached from v and v can be reached from u.

One (slow) way to do this is to call a DFS from each vertex independently.

Since DFS runs in time, and we run it on all n nodes, this approach runs in

Another (faster) way to do this is to run a "normal" DFS, followed by running a "backwards" DFS. In practice, this can be accomplished by either creating a copy of the graph with all the edges reversed, or creating a "reverse" opposite method (where we pass a vertex and an edge, and get the opposite vertex).

Using this approach requires us to run two DFS searches (one forward, one reverse). Since DFS runs in time, running two DFS runs in

Dietel Chapter 3: Connectivity

A better/more helpful definition of connectivity: "a graph is k-connected if any two of its vertices can be joined by k independent paths."


  • Structure of 2-connected graphs
  • Structure of 3-connected graphs
  • Menger theorem - states that the definition given above, and the definition saying we need at least k vertices to disconnect a k-connected graph, are in fact equivalent.
  • Number of H-paths in a given subgraph H
  • Number of edge-disjoint spanning trees
  • Existence of disjoint paths linking several given pairs of vertices

2-connected graphs and subgraphs:

Blocks, analogues of components (maximal connected subgraphs of a graph)

Proposition: a graph is 2-connected if and only if it can be constructed from a cycle by successively adding H paths to graphs H already constructed.

3-connected graphs and subgraphs

Lemma: if G is 3-connected and cardinality of G is larger than 4, then G has an edge such that G without e is again 3-connected.

Theorem: a graph G is 3-connected if and only if there exists a sequence G0 to Gn of graphs with the two properties that... G0 has cardinality 4, and Gn = G

Theorem above is essential part of Tutte's wheel theorem (Graphs of the form are called wheels, so is the smallest wheel.)

The cycle space of 3-connected graph is generated by non-separating induced cycles

We call C a fundamental triangle if it is an induced cycle C on the graph and if

Every fundamental triangle is a basic cycle in G.

Menger's Theorem

Theorem: Let be a graph and .. Then the maximum number of vertices separating A from B in G is equal to the maximum number of disjoint A-B paths in G.

Global version:

  • A graph is k-connected if and only if it contains k independent paths between any two vertices.
  • A graph is k-edge-connected if and only if it contains k edge-disjoint paths between any two vertices.

Mader's Theorem

An analogy to Menger's theorem; we ask, given a graph G with an induced subgraph H, how many independent H-paths can we find in G?

Theorem: Given a graph G with an induced subgraph H, there are always independent H-paths in G, where denotes the upper bound on the minimum number of H-paths in G.

(Again with the deluge of specialized, one-off notation.)

Edge disjoint spanning trees

Theorem: a multigraph contains k edge-disjoint spanning trees if and only if for every partition P of its vertex set it has at least cross-edges.

To ensure the existence of k edge-disjoint spanning trees, it suffices to raise the edge-connectivity to 2k.

Every 2k-edge-connected multigraph G has k edge-disjoint spanning trees.

Paths between given pairs of vertices:

  • Graph with at least 2k vertices is k-linked if each 2k distinct vertices contain k disjoint paths.
  • Not just asking for k disjoint paths between two sets of vertices: we are insisting these paths also link specified pairs of end vertices.
  • Condition of being k-linked is much stronger than being k-connected

(Not even going to try to slog through the rest of this chapter.)