Thursday, February 6, 2014

Fáry's theorem and graph connectivity

1Fáry's theorem¶

Any planar graph has a planar drawing in which all the lines are straight.

Proof: First, we assume that $\delta(G) \geq 3$. Here's why: If $G$ is disconnected, then we can consider each component as a separate graph; thus, we assume that $G$ is connected, in which case $\delta(G) \geq 1$. Suppose there exists a vertex $v \in V$ such that $\deg(v) = 1$. Then you can just draw an infinitely small straight line from $v$ to its only neighbour. Formally, if we induct on the size of $G$, then $G-v$ must have a straight planar drawing, and we can just attach $v$ to its neighbour with a short straight line.

Alternatively, suppose there exists a $v \in V$ such that $\deg(v) = 2$. Let $v$'s neighbours be $a$ and $b$. Remove $v$, and add an edge between $a$ and $b$ (if there isn't one already), and call this new graph $G'$. By induction, $G'$ has a straight line drawing. Then we just add back $v$, either in the middle of the straight line between $a$ and $b$, or like right next to it if $a-b$ is already connected.

So that covers the cases there $\delta G < 3$. Let's now work under the assumption that $\deg(G) \geq 3$, and induct on the number of vertices, $n$, in $G$.

Base case: $n \leq 5$. We can assume that $G$ is triangulated, i.e., every face has 3 edges. If this is not the case, then we can just add dummy edges to $G$ and remove them from the straight line drawing we found. (Why? And what about faces with more than 3 edges?)

Next, we show by induction that for any face $\{x, y, z\}$ of $G$, there exists a straight line drawing where $\{x, y, z\}$ is the outer face.

(This is actually a stronger conjecture than the one we are seeking to prove; this sometimes occurs in inductive proofs, because it makes the induction step easier. In other words, this gives us a stronger induction hypothesis.)

Nvm I don't care

2Graph connectivity¶

Vertices $i$ and $j$ and $k$-connected if there exist $k$ vertex-disjoint paths from $i$ to $j$.

An entire graph is $k$-connected if every pair of vertices is $k$-connected.

A set $U \subseteq V$ is an $i-j$ separator if $i$ and $j$ are in different components of $G-U$. So if you try to get from $i$ to $j$, you need to use a vertex in $U$ at some point. Another way of thinking about it: if you remove $U$ from $G$, there's no way to get from $i$ to $j$.

2.1Menger's theorem¶

Given $G = (V, E)$ and $s, t \in V$, the maximum number of disjoint $s-t$ paths is equal to the minimum size of an $s-t$ separator.

(This is a simple case of max-flow min-cut.)

Proof: ($\max \leq \min$) If $U$ is an $s-t$ separator then every $s-t$ path uses $\geq 1$ vertex in $U$. So the maximum number of disjoint paths is $\leq |U|$.

($\max \geq \min$) Let the max be $k$. The trick is to take $G$ and draw an auxiliary bipartite graph $H$, fuck it, this proof is too long