We investigate the vertex-connectivity of the graph of f-monotone paths on
a cl-polytope P with respect to a generic functional f. The third author ha
s conjectured that this graph is always (d - 1)-connected. We resolve this
conjecture positively for simple polytopes and show that the graph is 2-con
nected for any d-polytope with d greater than or equal to 3. However,we dis
prove the conjecture in general by exhibiting counterexamples for each d gr
eater than or equal to 4 in which the graph has a vertex of degree two.
We also re-examine the Baues problem for cellular strings on polytopes, sol
ved by Billera, Kapranov and Sturmfels. Our analysis shows that their posit
ive result is a direct consequence of shellability of polytopes and is ther
efore less related to convexity than is at first apparent.