Kvant Math Problem 403

Verified: no
Verdicts: SKIP + SKIP
Solve time: 8m44s
Source on kvant.digital

Problem

Prove that if, in a convex polyhedron, an even number of edges emanates from each vertex, then the intersection of the polyhedron with any plane that does not pass through any of its vertices is a polygon with an even number of sides.

Exploration

A convex polyhedron has the property that every vertex has even degree. The section of the polyhedron by a plane not passing through any vertex is a polygon. The task is to prove that this polygon has an even number of sides.

The condition on vertex degrees suggests graph theory. The edges and vertices of the polyhedron form a planar graph on the sphere. A graph in which every vertex has even degree is Eulerian. The section polygon is obtained by intersecting the plane with certain edges of the polyhedron. The number of sides of the section polygon equals the number of polyhedron edges cut by the plane.

A first attempt is to count directly the edges cut by the plane. Let the plane divide space into two open half-spaces. Assign to each vertex the sign $+$ or $-$ according to the side of the plane on which it lies. Since the plane contains no vertex, every vertex receives exactly one sign. An edge is cut by the plane exactly when its endpoints have opposite signs.

The problem then becomes purely graph-theoretic: in a graph all of whose vertex degrees are even, show that the number of edges joining a $+$ vertex to a $-$ vertex is even.

Testing small examples supports this. In a cycle, every time one crosses from a block of $+$ vertices to a block of $-$ vertices, one must later cross back, producing an even number of crossing edges. For a general Eulerian graph, a counting argument seems more robust.

The delicate point is to justify rigorously that the number of cut edges is even. At a positive vertex $v$, let $c(v)$ be the number of cut edges incident with $v$. Since the total degree of $v$ is even, the parity of $c(v)$ is the same as the parity of the number of non-cut edges incident with $v$. All non-cut edges at a positive vertex connect it to positive vertices, hence contribute twice to the total number of such incidences. Consequently the sum of the numbers $c(v)$ over all positive vertices is even. But this sum counts each cut edge exactly once, so the number of cut edges is even. This appears to be the core insight.

Problem Understanding

We are given a convex polyhedron such that an even number of edges emanates from every vertex. A plane intersects the polyhedron and does not pass through any vertex. The intersection is a polygon. We must prove that this polygon has an even number of sides.

This is a Type B problem.

The core difficulty is to translate the geometric statement about a planar section into a combinatorial statement about the edge graph of the polyhedron and then exploit the parity condition on vertex degrees.

Proof Architecture

The first lemma is that the number of sides of the section polygon equals the number of edges of the polyhedron intersected by the plane. The reason is that every vertex of the section polygon lies on a unique edge of the polyhedron cut by the plane, and consecutive vertices of the section polygon correspond to distinct cut edges.

The second lemma is that an edge of the polyhedron is intersected by the plane if and only if its endpoints lie in opposite open half-spaces determined by the plane. This follows from convexity of a line segment.

The third lemma is that in any graph whose vertex degrees are all even, for any partition of the vertices into two classes, the number of edges joining the two classes is even. This is proved by a parity count at the vertices of one class.

The hardest step is the third lemma, because it is where the parity condition must be converted into a parity statement about crossing edges.

Solution

Let $P$ be the convex polyhedron and let $\pi$ be the given plane. Since $\pi$ does not pass through any vertex of $P$, every vertex of $P$ lies in one of the two open half-spaces determined by $\pi$.

Denote these two half-spaces by $H_+$ and $H_-$. Assign to each vertex the sign $+$ or $-$ according as it belongs to $H_+$ or $H_-$.

Since $P$ is convex, the intersection $P \cap \pi$ is a convex polygon. Each vertex of this polygon is obtained as the intersection of $\pi$ with an edge of $P$ whose endpoints lie on opposite sides of $\pi$. Conversely, if an edge of $P$ has endpoints on opposite sides of $\pi$, then the segment intersects $\pi$ in exactly one point, which is a vertex of the section polygon. Hence the number of sides of the section polygon is equal to the number of edges of $P$ whose endpoints have opposite signs.

It remains to prove that the number of such edges is even.

Consider the graph formed by the vertices and edges of the polyhedron. Every vertex of this graph has even degree by hypothesis.

Let $E_c$ be the set of edges whose endpoints have opposite signs. For each positive vertex $v$, let $c(v)$ be the number of edges of $E_c$ incident with $v$.

Since $\deg(v)$ is even,

$$c(v)\equiv \deg(v)-c(v)\pmod 2.$$

The quantity $\deg(v)-c(v)$ is the number of edges incident with $v$ whose other endpoint is also positive.

Summing over all positive vertices, we obtain

$$\sum_{v\in H_+} \bigl(\deg(v)-c(v)\bigr).$$

Every edge joining two positive vertices contributes $2$ to this sum, and no other edge contributes. Hence the sum is even.

Because every $\deg(v)$ is even, the sum

$$\sum_{v\in H_+} \deg(v)$$

is also even. Therefore

$$\sum_{v\in H_+} c(v) = \sum_{v\in H_+} \deg(v) - \sum_{v\in H_+} \bigl(\deg(v)-c(v)\bigr)$$

is even.

On the other hand, every edge of $E_c$ has exactly one positive endpoint, so it is counted exactly once in the sum $\sum_{v\in H_+} c(v)$. Consequently

$$|E_c|=\sum_{v\in H_+} c(v),$$

and therefore $|E_c|$ is even.

Thus the number of edges of $P$ cut by the plane $\pi$ is even. Since this number equals the number of sides of the section polygon, the section polygon has an even number of sides.

This completes the proof.

∎

Verification of Key Steps

The first delicate step is the identification of the sides of the section polygon with the edges of the polyhedron cut by the plane. A vertex of the section polygon arises where the plane meets an edge of the polyhedron. Because no vertex of the polyhedron lies on the plane, such an intersection can occur only in the interior of an edge. Each cut edge contributes exactly one intersection point. The vertices of the section polygon are precisely these points, so the number of polygon sides equals the number of cut edges.

The second delicate step is the parity count. For a positive vertex $v$, the number $\deg(v)-c(v)$ counts positive-positive edges incident with $v$. Summing over all positive vertices counts each positive-positive edge twice and nothing else. The resulting sum is therefore even. Forgetting the factor of two would destroy the argument.

The third delicate step is the identity

$$|E_c|=\sum_{v\in H_+} c(v).$$

Each crossing edge has one positive endpoint and one negative endpoint. Counting incidences only at positive vertices counts every crossing edge exactly once. Counting at all vertices would count each crossing edge twice and would not directly yield the desired parity statement.

Alternative Approaches

A graph-theoretic reformulation gives a shorter proof. The edge graph of the polyhedron is Eulerian because every vertex has even degree. Any Eulerian graph decomposes into edge-disjoint cycles. After assigning signs to vertices according to the side of the plane, each cycle contains an even number of edges whose endpoints have opposite signs, because every time the cycle passes from one side to the other it must later return. Summing over all cycles shows that the total number of crossing edges is even. The rest of the geometric argument is unchanged.

The main approach is preferable because it avoids the theorem on decomposition into cycles and reduces the parity statement to a single counting argument at the vertices. It uses only the given hypothesis that all vertex degrees are even.