问题描述 #

Consider a graph $G(V,E)$ with $n:= \lvert V(G) \rvert$ and the corresponding polytope
$$Q := \left{ x \in [0, 1]^{E} : \sum_{e \in E} x_e = n - 1, , \sum_{e \in \delta(X)} x_e \geq 1 \text{ for all } \emptyset \subseteq X \subseteq V \right}.$$

Show that $Q$ is not integral.

Hint: Use the graph Let $G = (V, E)$ be a graph with $V = {0, 1, 2, 3, 4}$ and $E = { {i, i+1} \mod 5 \mid i = 0, \ldots, 4} \cup {0, 3}$.
The only edges with non-zero weights are ${0, 1}, {1, 2}$, and ${2, 3}$, each with a weight of $1$. (See below for a sketch of the graph.)

我不太理解提示里给出的图要怎么用来证明多面体$Q$不是整数的，能不能详细解释一下这个思路？

解答 #

嗨，我来一步步帮你理清楚这个提示的用法，核心思路其实很简单：只要找到一个属于$Q$但分量不全是整数的点，就能证明$Q$不是整数多面体——毕竟整数多面体的所有顶点都是整数点，不可能存在纯分数的可行点。

1. 先把提示里的图拆解清楚 #

这个图$G$是5个顶点的环（0-1-2-3-4-0）再加上一条弦边${0,3}$，总共6条边。顶点数$n=5$，所以$Q$的第一个约束是所有边的$x_e$之和必须等于$n-1=4$。

2. 构造符合要求的非整数可行点 #

我们给每条边都赋值$\boldsymbol{x_e = \frac{2}{3}}$，也就是所有边的权重都是$\frac{2}{3}$。现在来验证这个点满足$Q$的所有约束：

• 总边和约束：6条边每条都是$\frac{2}{3}$，总和是$6 \times \frac{2}{3} = 4$，刚好等于$n-1$，满足第一个条件。
• 割约束：这个图是2-连通的（任意两个顶点之间至少有两条不相交的路径），所以任何非空真子集$X$对应的割集$\delta(X)$（连接$X$和$V\setminus X$的边）至少包含2条边。割集的边和就是$2 \times \frac{2}{3} = \frac{4}{3} \geq 1$，完全满足第二个约束。
• 区间约束：$\frac{2}{3}$显然在$[0,1]$之间，符合要求。

3. 得出结论 #

这个点$\boldsymbol{x = (\frac{2}{3}, \frac{2}{3}, \frac{2}{3}, \frac{2}{3}, \frac{2}{3}, \frac{2}{3})}$（对应6条边）属于$Q$，但所有分量都是分数，不是整数。这就直接说明$Q$不是整数多面体——因为整数多面体里的所有点都是整数点的凸组合，不可能存在这样的纯分数可行点。

另外提一句，提示里提到的“only edges with non-zero weights are ${0,1},{1,2},{2,3}$ each with weight 1”大概率是笔误或者表述不全，上面的构造方法更直接清晰，完全贴合提示里的图的用法。

备注：内容来源于stack exchange，提问作者3nondatur