3
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

The answer is yes.


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\\ $$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Is there always an embeding with straight edges? I couldn't think of such an embeding fot the Goldner–Harary graph. $\endgroup$ – Olivier Roche Jan 14 at 10:13
  • 1
    $\begingroup$ Fary theorem $\endgroup$ – TheHolyJoker Jan 14 at 11:11
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.