Connectivity

Definition (Reachability)

We say vertex $u$ is reachable from $v$ if there is a Walk from $v$ to $u$.

Theorem (Connected Components)

For any $G$, you can partition vertices into its connected components such that given $u,v\in V$, $u$ is reachable from $v$ if it is in the same connected component.

Proof: This proof comes from the idea that connectivity is an equivalence relation.

1. $v$ is reachable from $v$, so it is reflexive
2. if $u$ is from reachable from $v$, then $v$ is reachable from $u$, so it is symmetric.
3. If $u$ is reachable from $v$, and $v$ to $w$, then there is a walk from $u$ to $w$, and thus reachable. It is transitive.

Thus, we can say that each connected component is an equivalence class. This gives us a formal way to partition $V$ into equivalence classes, such that $u,v$ are related iff they are in the same class.

graph LR
	u((u)) o--o mn[[many vertices]];
	mn o--o v((v))

Lemma (Odd Loops, Odd Cycle)

If $G$ has a loop of odd length, it has a cycle of odd length.

Proof: If there are no repeated vertices, then it is automatically a cycle. Suppose not. Consider

graph LR;
	v((v)) o--P1--o w((w));
	v o--P3--o w;
	w o--P2--o w;

where $P\{1,2,3\}$ are walks and $w$ is our repeated vertex. We have two loops, $P2$ and $P1,P3$. Since $|P1|+|P2|+|P3|$ is odd, either at least one is odd or all are odd. If $P2$ is odd, we can repeat the process and obtain an odd cycle.

If the sole odd walk is $P1$ xor $P2$, we are done.

We use loop here to mean “a walk that starts and ends at the same vertex, but may repeat edges/vertices.”

Theorem (Bipartite Cycles)

Graph $G$ is bipartite iff it contains no odd length Cycle.

Proof: $(⟹)$ Suppose we have some cycle of length $n$ that is odd, such that $v_1,v_2,\dots ,v_n,v_1$ is our cycle. WLOG, if $v_1$ is white, $v_2$ is black. In general, all odd vertices are white, and all even vertices are black. But then $v_n$ is odd and so it is white. But then our edge $(v_n,v_1)$ is invalid (white to white), and so it cannot be bipartite.

$(⟸)$ WTS that

$$\text{no odd cycles }⟹\text{bipartite}$$

Assume $G$ is connected and has no odd cycles. Pick some vertex $v$ in this partition. We pick another $w$ in this partition, and as it is connected there exists a $v-w$ Walk $P$. If $|P|$ is even, then let $w$ be white. If $|P|$ is odd, let $w$ be black.

We can have many $v-w$ paths. I claim that all paths will have even length or odd length. Suppose by contradiction that we have two walks, one with even and odd path.

graph LR;
	u((u)) o--o p1[[even path]];
	u o--o p2[[odd path]];
	p1 o--o v((v));
	p2 o--o v;

But then we have a loop of odd length as $\text{odd}+\text{even}=\text{odd}$. Note that this is a loop because the odd path may use some of the vertices in the even path.

Using Lemma (Odd Loops, Odd Cycle), the odd path gives us an odd cycle. But this contradicts the premise that we have no odd cycles, and so all paths must be even or odd.

So if all paths from $v$ to $w$ are even, color $v$ white. We need to show that any $(u,w)$ edge, it must have different colors. WLOG, we color $w$ white if any $v-w$ path is even, and $w$ black if any path $v-w$ is odd.

Let $P_u$ be the $v-u$ path. Now consider path $P_u+(u,w)$, of length $|P_u|+1$. If $|P_u|$ was odd, then $|P_u|+1$ is even, then $w$ is black, and $u$ is white, and vice versa.

Since $u$ is arbitrary, every edge has different coloring, and the graph is bipartite.

If $G$ is not connected then we can split it to its connected components and repeat the process. Then each connected component is bipartite.

Definition (Bridge)

A bridge is an edge where if you removed it from the Graph, it would make the graph no longer connected (create one more connected component).