# adding edges to a planar graph

Let G be a finite, planar, disconnected graph with two components.

Is it always possible to add an edge to the graph to make it connected and still planar?

Rigorous proofs regarding planarity of a graph usually use non-trivial theorems such as Jordan curve theorem, and theorems about embedding, which I will avoid, and therefore will give intuition, and not a full answer.

## Constructive Proof

Denote the two disconnect planar graphs by $$G,H$$. Since they are both planar, one could embed them on the plane $$\mathbb R^2$$ with straight edges (and not just curves) This is equivalent to stating:

1. $$G$$ could be embedded in $$\{(x,y)\in\mathbb R^2|x>0\}$$ with straight edges.
2. $$H$$ could be embedded in $$\{(x,y)\in\mathbb R^2|x<0\}$$ with straight edges.

Now Denote by $$F_1,F_2$$ thier outer faces, with bouderies $$A\subset V(G),B\subset V(H)$$.

Proposition one could connect by an edge the two faces.

## Proof:

Pick $$v\in G$$ whose $$x$$ coordinate is minimal (maybe not unique). Pick $$u\in H$$ whose $$x$$ coordinate is maximal (maybe not unique). Connect them by a straight edge.
By the choice of $$v,u$$, and the fact all previous edges were segments, we can conclude the new graph is also planar, by the new obtained embedded.

## Existence Proof

One a second thought, I think it might be easier to use Kuratowski's theorem and Wagner theorem and prooving:

By adding one edge between two disconnected graphs $$G,H$$, you could not form $$K_5, K_{3,3}$$ subdivision or minor.

A proof sketch would be: $$\forall v\in G\ \ \deg_H(v)=0\\ \forall u\in H\ \ \deg_G(v)=0\\$$

• Is there always an embeding with straight edges? I couldn't think of such an embeding fot the Goldner–Harary graph. – Olivier Roche Jan 14 at 10:13
• Fary theorem – TheHolyJoker Jan 14 at 11:11

Let $$C,C'$$ the two connected components of $$G$$. By Fáry's theorem, there is an embedding into the plane that maps edges to line segments. We will identify $$G$$ with its image under such an embedding. WLOG, the convex hull $$H$$ of $$C$$ and the convex hull $$H'$$ of $$C'$$ have empty intersection (just translate $$C'$$ out of $$H$$). Let's call $$d$$ the Euclidean distance.

Both $$H$$ and $$H'$$ are polygons whose edges are edges of $$C$$ and $$C'$$ respectively. Take vertices $$v, v'$$ in the boundaries of $$H,H'$$ respectively such that $$d(v, v')$$ is minimal.

Clearly, if you add the edge $$(v,v')$$ to your graph, it is connected and still planar.

• Notice that the choice of $(v,v')$ might not be unique (eg if $H$ and $H'$ have parallel edges). – Olivier Roche Jan 14 at 9:15
• I think you have to state the edges in the embedding are segments and not curves (which they are in general embedding). – TheHolyJoker Jan 14 at 9:21
• @TheHolyJoker thank you! It looks right, now. – Olivier Roche Jan 14 at 12:26
• @TheHolyJoker Also, thanks for the nice edit. :) – Olivier Roche Jan 14 at 13:15