Edges of the convex hull of a finite point set I'm looking for a formal proof of a statement that seems obvious (and yet may be wrong) to make sure one of my algorithms is correct.
Given a set S of N points in  $\mathbb{R}^3$, suppose we have a plane such as:


*

*two points among the set S belong to that plane

*all the N points are located on the same side relatively to this plane


Prove that at least one edge of the convex hull of the set S belongs to that plane.
 A: Let $H$ be the convex hull, that is, the smallest convex set that includes all the $N$ points of $S$. Set $V$, $E$, $F$, $I$ be the sets of vertices, edges, faces and interior of $H$ respectively, where $V$, $E$, $F$, $I$ are pairwise disjoint that is $H = V \uplus E \uplus F \uplus I$. For example $H = \bar{I}$, that is the closure of $I$, $V = \bar{E}-E$, $V \uplus E = \bar{F}-F$ and $V \uplus E \uplus F = \bar{I}-I$. Furthermore, denote the aforementioned plane as $P$ and let $A,B \in P \cap H$ be the two vertices from the question and $AB$ be the open segment between them.

First, because of convexity, $$H\text{ lies on one side of the plane }P. \tag{1}$$ Let's introduce a Cartesian coordinate system such that $P = \{ p \in \mathbb{R}^3 \mid \pi_z(p) = 0 \}$ and $S \subset \{ p \mid \pi_z(p) \geq 0 \}$. Then $\forall p \in H.\ \pi_z(p) \geq 0$ and thus $H \subset \{p \mid \pi_z(p) \geq 0 \}$.
Also, because of convexity $AB \subset H$ and $AB \subset P$ (plane is convex too).
Consider the following cases:


*

*$AB \cap V \neq \varnothing$. Impossible (please remember that $A,B \notin AB$).

*$AB \cap E \neq \varnothing$. In this case we are done (see lemma below).

*$AB \cap E = \varnothing$. I will try to show that in this case $AB \cap F \neq \varnothing$ and therefore $F \cap P \neq \varnothing$ which implies the existence of desired edge (the faces are bounded with edges).
We know that $AB \subset F \uplus I$. Let's assume that $AB \cap I \neq \varnothing$. Then, because $I$ is open, for any $p \in AB \cap I$ there exists a small ball with center at $p$ and non-zero radius that is contained in $I$. However, this contradics (1). Then we have $AB \cap I = \varnothing$ and thus $AB \subset F$. Finally $AB \cap F \subset P$, so $E \supset (\bar{F}-F)\cap P \neq \varnothing$. The non-emptiness of the last set implies the existence of the desired edge via the following lemma.

Lemma. Existence of $p \in E \cap P$ implies the existence of an edge $e \ni p$ such that $e \subset P$.
Proof. Let $e$ be any edge such that $p \in e$. Then, because $e$ is open as one dimensional set, there exists a 1D open ball with center at $p$ and non-zero radius, that is contained in $e$. This forces that $e$ is parallel to $P$, but having $p$ as common point, $e \subset P$.

Here are the details, I hope you will enjoy it ;-)
