Kvant Math Problem 75

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m19s
Source on kvant.digital

Problem

a) Prove that in any convex polyhedron, the sum of the lengths of all edges is greater than three times the diameter. (The diameter of a polyhedron is defined as the greatest length among all segments with endpoints at the vertices of the polyhedron.)

b) Prove that for any two vertices $A$ and $B$ of a convex polyhedron, there exist three broken lines, each following the edges of the polyhedron from $A$ to $B$, and no two of them share an edge.

c) Prove that if two edges of a convex polyhedron are removed, then for any two of its vertices $A$ and $B$, there exists a broken line connecting $A$ to $B$ along the remaining edges.

d) Prove that in problem b) it is possible to choose three broken lines that have no vertices in common pairwise, except for the endpoints $A$ and $B$.

A. G. Kushnirenko

Exploration

Part a) suggests looking at projections. If a segment joining two vertices realizes the diameter $D$, then every edge contributes at most its projection onto the direction of that segment. The total positive projection of all edges should control $D$. A tetrahedron gives a useful test. If the diameter is realized by vertices $A,B$, then there are at least three edge-disjoint paths from $A$ to $B$ around the boundary, and each path has length at least $AB=D$. Summing their lengths gives at least $3D$. Since the total edge sum counts every edge at most once among those paths, this proves the claim immediately if part b) is already known. So the real content is graph-theoretic connectivity of the edge graph of a convex polyhedron.

Part b) is reminiscent of Menger's theorem or Whitney's theorem for planar 3-connected graphs. Since the problem is elementary in style, there should be a direct geometric proof. A convex polyhedron intersects a plane through $A$ and $B$ in a convex polygon or a union of polygons. If the plane is chosen generically, perhaps the boundary gives two disjoint paths. But three are required.

A more promising approach uses the local structure of faces. Remove the vertices $A,B$ from the graph of the polyhedron. The remaining graph should stay connected. Then each neighbor of $A$ can reach a neighbor of $B$, and because every vertex of a convex polyhedron has degree at least $3$, one expects three independent routes. Still, proving this directly without advanced graph theory may become messy.

Steinitz's theorem says the graph of a convex polyhedron is exactly a planar 3-connected graph. Then parts b), c), d) become immediate consequences of Menger's theorem. Since this is a Kvant problem, using the planar Jordan curve argument behind 3-connectivity is probably more appropriate than quoting full theorems.

The key fact is that the graph of a convex polyhedron is 3-connected. Then:

For b), edge-version Menger gives three edge-disjoint $A$-$B$ paths.

For c), removing two edges cannot disconnect a 3-edge-connected graph.

For d), vertex-version Menger gives three internally vertex-disjoint $A$-$B$ paths.

So everything reduces to proving 3-connectivity. A classical elementary proof goes as follows. Suppose removing two vertices $P,Q$ disconnects the graph. Then there are vertices $X,Y$ in different components. Intersect the polyhedron with a plane separating $X,Y$ from the line $PQ$. The section polygon must cross from one component to another without using $P,Q$, contradiction. This needs careful formulation.

There is also Balinski's theorem for polytope graphs, but that is stronger machinery than needed.

The most delicate point is proving 3-connectivity rigorously from convexity alone, without silently using a deep theorem. Once that is established, the rest is routine graph theory.

Problem Understanding

This is a Type B problem. Each part asks for a proof of a structural property of convex polyhedra.

Part a) asks to compare the total edge length with the diameter, meaning the maximum distance between two vertices.

Part b) asks to prove the existence of three edge-disjoint edge-paths between any two vertices.

Part c) asks to prove that deleting any two edges never disconnects the graph of the polyhedron.

Part d) strengthens part b) by requiring the three paths to be internally vertex-disjoint.

The core difficulty is the connectivity structure of the graph of a convex polyhedron. Parts b), c), and d) are all consequences of the fact that the graph is 3-connected. Part a) then follows by combining this connectivity with the triangle inequality.

Proof Architecture

The first lemma states that the graph of a convex polyhedron remains connected after deletion of any two vertices.

The proof uses a generic plane section separating two vertices from the remaining vertices; the section polygon produces a connected cycle avoiding the deleted vertices.

The second lemma states that a graph remaining connected after deletion of any two vertices contains three internally vertex-disjoint paths between any two distinct vertices.

The proof is an application of Menger's theorem in the vertex form.

The third lemma states that three internally vertex-disjoint paths are automatically edge-disjoint, and that deleting two edges cannot destroy all three paths simultaneously.

The proof counts how many paths can be affected by one deleted edge.

The hardest point is the first lemma. A careless argument can fail if the cutting plane passes through vertices or edges of the polyhedron, so the plane must be chosen in general position.

Solution

Let $G$ be the graph formed by the vertices and edges of the convex polyhedron.

We first prove that $G$ is $3$-connected.

Assume that after deletion of two vertices $P,Q$, the remaining graph becomes disconnected. Then the remaining vertices split into two nonempty sets $U,V$ such that every path joining a vertex of $U$ to a vertex of $V$ passes through $P$ or $Q$.

Choose vertices $X\in U$ and $Y\in V$. Since the polyhedron is convex, the segment $XY$ lies inside the polyhedron.

Choose a plane $\pi$ passing through the line $XY$ and such that:

$$\pi \cap {P,Q}=\varnothing,$$

and $\pi$ contains no vertex of the polyhedron other than possibly $X,Y$, and no edge lies entirely in $\pi$.

The intersection of $\pi$ with the boundary of the polyhedron is a convex polygonal line arrangement whose connected components are closed polygons. Since the segment $XY$ lies inside the polyhedron, the line through $X,Y$ intersects the boundary of the polyhedron in exactly two points, and these two points belong to the same polygonal section. Hence $X$ and $Y$ lie on the boundary of the same polygonal section.

Traversing this polygonal section from $X$ to $Y$ in either direction yields two polygonal chains lying on faces of the polyhedron and avoiding $P,Q$. Whenever such a chain crosses an edge of the polyhedron, record that edge. Since no edge lies entirely in $\pi$, consecutive crossings correspond to adjacent faces sharing an edge. Thus each polygonal chain determines a path in the graph $G$ from $X$ to $Y$ avoiding $P,Q$.

This contradicts the assumption that every $X$-$Y$ path passes through $P$ or $Q$. Therefore deletion of any two vertices leaves $G$ connected. Hence $G$ is $3$-connected.

By the vertex form of Menger's theorem, for any two vertices $A,B$ there exist three internally vertex-disjoint paths joining $A$ and $B$. Since paths having no common internal vertices certainly have no common edges, part d) follows immediately, and part b) follows as well.

We now prove part c). Let two edges $e_1,e_2$ be removed. By part b), for any vertices $A,B$ there exist three edge-disjoint paths joining them. Each removed edge can destroy at most one of these paths, because the paths are edge-disjoint. After deletion of $e_1,e_2$, at least one of the three paths remains intact. Hence $A$ and $B$ are still connected.

Finally we prove part a). Let $A,B$ be vertices such that

$$AB=D,$$

where $D$ is the diameter of the polyhedron.

By part b), there exist three edge-disjoint paths $\Gamma_1,\Gamma_2,\Gamma_3$ joining $A$ and $B$.

For each $i$, the length of $\Gamma_i$ is at least $AB=D$, because the straight segment is the shortest curve joining two points. Thus

$$\ell(\Gamma_i)\ge D$$

for $i=1,2,3$.

Since the three paths are edge-disjoint, every edge of the polyhedron occurs in at most one of them. Therefore the sum $S$ of lengths of all edges of the polyhedron satisfies

$$S\ge \ell(\Gamma_1)+\ell(\Gamma_2)+\ell(\Gamma_3)\ge 3D.$$

Equality cannot occur. Indeed, equality would require that every $\Gamma_i$ have length exactly $D$, hence each $\Gamma_i$ would coincide geometrically with the segment $AB$. Since the three paths are edge-disjoint, this is impossible.

Therefore

$$S>3D.$$

This completes the proof.

∎

Verification of Key Steps

The first delicate point is the proof that deleting two vertices cannot disconnect the graph. The hidden danger is degeneration of the plane section. If the plane contains an edge of the polyhedron, then crossing data no longer produces a well-defined path in the graph. Choosing the plane in general position avoids this. Since only finitely many forbidden planes exist, one can perturb any plane through $XY$ slightly while still avoiding $P,Q$.

The second delicate point is the passage from the polygonal section to a graph path. Each time the section crosses an edge shared by two faces, the section passes from one face to another. The sequence of crossed edges is connected consecutively through common vertices inside each face boundary. This yields an actual edge-path in the graph. Without this justification, the argument would only produce a continuous curve on the surface, not a combinatorial path in the edge graph.

The third delicate point occurs in part a). The inequality

$$\ell(\Gamma_i)\ge AB$$

uses the fact that a broken line joining two points has length at least the straight segment between them. A careless proof might forget that the paths may self-intersect or revisit vertices, but the polygonal inequality remains valid for arbitrary broken lines. Equality would force every segment of the broken line to lie on the same straight line in the same direction, which cannot happen for three edge-disjoint paths.

Alternative Approaches

A shorter solution uses standard theorems from graph theory. Steinitz's theorem states that the graph of a convex polyhedron is planar and $3$-connected. Menger's theorem then gives three internally vertex-disjoint paths between any two vertices, immediately proving part d), hence part b). Part c) follows because deleting two edges cannot destroy all three edge-disjoint paths. Part a) follows by summing the lengths of the three paths.

Another approach to part a) avoids graph connectivity theorems. One may project all edges onto a line parallel to a diameter-realizing segment $AB$. Around every face, the total positive projection equals the total negative projection. Following the surface from the supporting plane at $A$ to the supporting plane at $B$ yields at least three disjoint chains with total projection at least $3AB$. This projection argument is more geometric but requires careful bookkeeping of orientations and face adjacencies.