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

2 Answers 2

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

$\endgroup$
2
  • $\begingroup$ Is there always an embeding with straight edges? I couldn't think of such an embeding fot the Goldner–Harary graph. $\endgroup$ Commented Jan 14, 2020 at 10:13
  • 1
    $\begingroup$ Fary theorem $\endgroup$ Commented Jan 14, 2020 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.

$\endgroup$
4
  • $\begingroup$ Notice that the choice of $(v,v')$ might not be unique (eg if $H$ and $H'$ have parallel edges). $\endgroup$ Commented Jan 14, 2020 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$ Commented Jan 14, 2020 at 9:21
  • $\begingroup$ @TheHolyJoker thank you! It looks right, now. $\endgroup$ Commented Jan 14, 2020 at 12:26
  • 1
    $\begingroup$ @TheHolyJoker Also, thanks for the nice edit. :) $\endgroup$ Commented Jan 14, 2020 at 13:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .