# Notes

## 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 ${\displaystyle O(n+m)}$ 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 ${\displaystyle O(n+m)}$ time, and we run it on all n nodes, this approach runs in ${\displaystyle O(n(n+m))}$

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 ${\displaystyle O(n+m)}$ time, running two DFS runs in ${\displaystyle O(n+m)}$

# 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."

Outline:

• 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 ${\displaystyle C^{n}*K^{1}}$ are called wheels, so ${\displaystyle K^{4}}$ 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 ${\displaystyle C=C^{3}}$

Every fundamental triangle is a basic cycle in G.

## Menger's Theorem

Theorem: Let ${\displaystyle G=(V,E)}$ be a graph and ${\displaystyle A,B\subseteq V}$.. 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.

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 ${\displaystyle M_{G}(H)}$ independent H-paths in G, where ${\displaystyle M_{G}(H)}$ 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 ${\displaystyle k(|P|-1)}$ 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.)