Directed polyhedral graph with $d^+(v) \geq 1$ and $d^- (v) \geq 1$

Question

Let $\Phi$ a convex polyhedron, with each edge being a vector (id est a directed line segment). For each vertex of the spatial object, let us define its $d^+(v)$ the number of vectors 'leaving' that vertex (id est those vectors that have the application point on the vertex we are studying) and $d^-(v)$ the number of vectors 'reaching' the vertex (id est those vectors that have the 'arrow' pointing to the vertex we are studying). If, for every vertex $v$ of the polyhedron $\Phi$, both $d^+(v)$ and $d^-(v)$ are greater than $1$, then there exists at least a face of the object which contains a directed cycle.

Note that all the notations used are those from Directed Graph Theory, including $d^+$ and $d^-$. I haven't managed to find a satisfactory approach, but I will analyze some particular cases I have tried.

The simplest polyhedron is the tetrahedron, which may also be represented (because we talk about graphs) as a triangle with a point inside it. Let's denote the triangle $ABC$ and $V$ the point inside.

Since $V$ has $d^+(V)$ and $d^-(V)$ are at least $1$, and since the total degree is $3$, there are exactly two pairs of segments between $PV and $A, B, C$ that are differently oriented.

Let us consider, WLOG, $\vec{VA}$, $\vec{BV}$ and $\vec{VC}$ the vectors that illustrate the directions of the segments between $V$ and the vertices of $\triangle ABC$. Since $B$ also have its degrees greter than $1$ and $\vec{BV}$ is 'leaving' $B$, at least one of $\vec{AB}$ and $\vec{CB}$ should exist in the edge set of our directed graph, either of them we'll chose, it will close a cycle. Therefore, we have proved the statement for the tetrahedron.

However, the general case is far more complicated and complex than these particular situations and I have trouble trying to extend the relation.

Answer 1

For any directed graph, these conditions on indegree and outdegree tell us that there must be a cycle. On a polyhedron, the cycle separates the surface into two parts, each one consisting of one or more faces.

Choose $C$ to be a cycle in which one of these parts contains as few faces as possible: call that part the "inside". We will try to prove that the "inside" is actually just a single face.

Well, if it's not a single face, then we can find the following: a vertex $v$ on the boundary of the $C$, such that one of $v$'s edges is inside $C$.

• Suppose that edge is a vector pointed out of $v$. In that case, follow that vector into $C$, and keep following vectors in accordance with their arrows until we either return to a vertex we've seen before, or return to the boundary of $C$. If we return to the boundary of $C$, follow $C$ around until we get back to $v$.

• Suppose that edge is a vector pointed into $v$. In that case, do the same thing as in the first case, but follow all vectors in the wrong direction: the opposite of the way they're pointing.

In both cases, the path we trace is a cycle $C'$, and one side of $C'$ is contained entirely "inside" $C$. Therefore $C'$ is a smaller cycle than $C$ - this contradicts our initial choice of $C$. As a result, the inside of $C$ must have been a single face to begin with.