Kvant Math Problem 903
A plane section of a convex polyhedron changes combinatorially only when the plane passes through a vertex.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 2m56s
Source on kvant.digital
Problem
Does there exist a convex polyhedron such that any cross-section by a plane not passing through a vertex is a polygon with
- an even number of sides,
- an odd number of sides?
A. A. Dorogovtsev
Exploration
A plane section of a convex polyhedron changes combinatorially only when the plane passes through a vertex. For a generic plane, the section is a polygon whose vertices are the intersection points of the plane with certain edges of the polyhedron.
The number of sides of a section is the number of edges of the polyhedron cut by the plane. Since the polyhedron is convex, all vertices on one side of the plane form a connected subgraph of the edge graph, and the same is true for the vertices on the other side. The cut edges are exactly the edges joining the two parts.
The parity of the number of cut edges suggests looking at graph theory. Let the vertices of the polyhedron be colored according to which side of the plane they lie on. Then the section has as many sides as there are edges joining opposite colors.
For a graph, the parity of the number of edges crossing a bipartition is determined by the parities of the degrees of the vertices in one part. Indeed, modulo $2$,
$$#(\text{crossing edges}) \equiv \sum_{v\in A}\deg(v).$$
Hence if every vertex of the polyhedron has even degree, every section should have an even number of sides.
Do convex polyhedra with all vertex degrees even exist? Yes. The octahedron has degree $4$ at every vertex.
For the odd case, suppose every section had an odd number of sides. Take a plane very close to a vertex $V$, separating $V$ from all other vertices. The section then cuts exactly the edges incident with $V$, so the number of sides equals $\deg(V)$. Thus every vertex must have odd degree.
Now use the handshaking lemma:
$$\sum \deg(V)=2E.$$
The left side would be a sum of an even number of odd integers if the number of vertices were even, and an odd number of odd integers if the number of vertices were odd. Since the sum is even, the number of vertices must be even.
But for any convex polyhedron, Euler's formula gives
$$V-E+F=2.$$
If every degree is odd, then $2E$ is even but not divisible by $4$ necessarily; this alone is not enough. A stronger argument is needed.
Consider a plane separating two adjacent vertices $A,B$ from all others. Such a section exists because the edge $AB$ lies on the boundary of a convex polyhedron. The section cuts
$$\deg(A)+\deg(B)-2$$
edges, since the edge $AB$ is not cut and is counted twice in the degree sum. If all degrees are odd, this number is even. Hence such a section has an even number of sides, contradicting the assumption that every section has an odd number of sides.
This appears to settle both parts.
The most delicate step is proving that a plane can be chosen so close to an edge $AB$ that exactly the vertices $A$ and $B$ lie on one side and all other vertices lie on the other. For a convex polyhedron, a supporting plane through the edge $AB$ exists; moving it slightly into the polyhedron produces the required separating plane.
Problem Understanding
We are asked whether there exists a convex polyhedron whose every plane section, provided the plane does not pass through a vertex, is always a polygon with a prescribed parity of the number of sides.
Part (1) asks for a polyhedron all of whose such sections have an even number of sides.
Part (2) asks for a polyhedron all of whose such sections have an odd number of sides.
This is a Type D problem. We must determine existence or nonexistence and justify it rigorously.
The core difficulty is relating the number of sides of a section to the combinatorial structure of the polyhedron. The crucial observation is that the number of sides equals the number of edges cut by the section plane.
The answer is that such a polyhedron exists for part (1), for example the octahedron, and no such polyhedron exists for part (2). The reason is that parity of section sizes is controlled by vertex degrees.
Proof Architecture
Lemma 1. For a plane section not passing through vertices, the number of sides of the section equals the number of edges of the polyhedron intersected by the plane. The vertices of the section polygon arise precisely from intersections with cut edges.
Lemma 2. If every vertex of a convex polyhedron has even degree, then every admissible section has an even number of sides. Modulo $2$, the number of cut edges equals the sum of the degrees of the vertices on either side of the section plane.
Lemma 3. The octahedron satisfies the hypothesis of Lemma 2. Every vertex of an octahedron has degree $4$.
Lemma 4. If a plane separates a single vertex $V$ from all remaining vertices, then the section has exactly $\deg(V)$ sides. The cut edges are precisely the edges incident with $V$.
Lemma 5. If a plane separates two adjacent vertices $A,B$ from all remaining vertices, then the section has exactly $\deg(A)+\deg(B)-2$ sides. The cut edges are exactly those incident with $A$ or $B$, except the common edge $AB$.
The hardest direction is proving nonexistence in part (2). The most vulnerable lemma is Lemma 5, because it requires the existence of a suitable separating plane.
Solution
Let $P$ be a convex polyhedron, and let $\pi$ be a plane not passing through any vertex of $P$.
The intersection $P\cap\pi$ is a convex polygon. Its vertices are exactly the intersection points of $\pi$ with those edges of $P$ whose endpoints lie on opposite sides of $\pi$. Hence the number of sides of the section polygon is equal to the number of edges of $P$ cut by $\pi$.
We first answer part (1).
Suppose every vertex of $P$ has even degree. Let the vertices of $P$ be partitioned into two sets $A$ and $B$ according to the side of $\pi$ on which they lie.
Let $N$ denote the number of edges cut by $\pi$. Modulo $2$,
$$N \equiv \sum_{v\in A}\deg(v).$$
Indeed, every edge with both endpoints in $A$ contributes $2$ to the sum on the right, every edge with both endpoints in $B$ contributes $0$, and every edge joining $A$ and $B$ contributes $1$. Therefore the parity of the sum equals the parity of the number of crossing edges.
Since every degree is even,
$$\sum_{v\in A}\deg(v)\equiv 0 \pmod 2,$$
hence
$$N\equiv 0 \pmod 2.$$
Thus every section polygon has an even number of sides.
Now consider the octahedron. Each of its six vertices is incident with four edges, so every vertex has degree $4$. Therefore every plane section not passing through a vertex has an even number of sides.
Thus a polyhedron with the property required in part (1) exists.
For part (2), assume that a convex polyhedron $P$ has the property that every admissible section has an odd number of sides.
Choose a vertex $V$. Since $P$ is convex, a plane can be placed sufficiently close to $V$ so that $V$ lies on one side of the plane and all other vertices lie on the other side. The cut edges are then exactly the edges incident with $V$. Consequently the section has
$$\deg(V)$$
sides.
By assumption this number is odd. Since $V$ was arbitrary, every vertex of $P$ has odd degree.
Next choose an edge $AB$ of $P$. A supporting plane through the edge $AB$ exists because $AB$ lies on the boundary of the convex polyhedron. Move this plane slightly into the interior of the polyhedron. Then $A$ and $B$ lie on one side of the new plane and all remaining vertices lie on the other side.
The cut edges are precisely all edges incident with $A$ or $B$, except the edge $AB$ itself. Therefore the section has
$$\deg(A)+\deg(B)-2$$
sides.
Since $\deg(A)$ and $\deg(B)$ are odd,
$$\deg(A)+\deg(B)-2$$
is even.
Hence this section has an even number of sides, contradicting the assumption that every admissible section has an odd number of sides.
The contradiction shows that no convex polyhedron can satisfy the requirement of part (2).
The answers are
$$\boxed{\text{(1) Yes, for example the octahedron; \quad (2) No such polyhedron exists.}}$$
Verification of Key Steps
For the parity computation in part (1), let $A$ be the set of vertices on one side of the section plane. Each edge entirely inside $A$ contributes $2$ to $\sum_{v\in A}\deg(v)$, each edge entirely outside $A$ contributes $0$, and each cut edge contributes $1$. Reducing modulo $2$ leaves exactly the number of cut edges. Forgetting to work modulo $2$ would make the argument incorrect.
For the section isolating a single vertex $V$, the plane must be chosen sufficiently close to $V$. Since the set of all other vertices is finite, there exists a plane separating $V$ from the convex hull of the remaining vertices. The only edges joining the two sides are the edges incident with $V$, giving exactly $\deg(V)$ sides.
For the section isolating the endpoints of an edge $AB$, the danger is overlooking additional vertices near the separating plane. Starting from a supporting plane through the edge $AB$ and shifting it slightly toward the interior ensures that only $A$ and $B$ remain on one side. The cut edges are then exactly those incident with $A$ or $B$, except $AB$. Counting them gives $\deg(A)+\deg(B)-2$.
Alternative Approaches
Instead of using the parity identity
$$N\equiv\sum_{v\in A}\deg(v)\pmod 2,$$
one may invoke the graph-theoretic fact that a graph has only even edge cuts if and only if every vertex has even degree. The edge graph of a convex polyhedron is connected, so a polyhedron whose vertices all have even degree automatically has all section sizes even. The octahedron again provides an example.
For the nonexistence part, one may first deduce from sections isolating single vertices that every vertex degree is odd. Then any section isolating the endpoints of an edge produces an even number of sides. This argument is essentially local and avoids using Euler's formula or any global combinatorial information about the polyhedron. The local degree-counting approach is shorter and makes the contradiction immediate.