• The version I have.
• The official current version.

I solved this problem mentally over lunch because it was semi-relevant to my work at MITRE. This means you can solve it, too. Do so; if you give up, then (and only then) you can ask me for the solution.

First, the background. Given a graph G(V,E), choose a source S and a sink T. The minimum cut is defined as the least set of edges that must be removed from G so that no flow can be pushed from S to T. A graph is connected if, for any pair of points in that graph, there exists a sequence of edges connecting the pair. Finally, the edge connectivity of a connected graph is the least number of edges that can be removed from the graph to disconnect it.

A standard edge connectivity algorithm is as follows: choose one point as the source, and let the sink vary over the remaining V-1 vertices. Find the min cut for each of the V-1 source and sink combinations. The minimum of these min cuts is the edge connectivity.

Finally, the problem. For a given graph, perform the edge connectivity algorithm, considering for each min cut only the number of edges, not which ones they are. Prove that these min cuts are not all unique. You may assume that the graph is connected and that all edges are bidirectional.

Update: Richard spoiled this problem by looking up S. So I am no longer offering money for the proof, though I would like to see one. But the dime offer still stands for the second part.

Yes, I invented this problem; no, I have not solved it yet. A nickel to the first person who does so!

Define F₀=0, F₁=1, and F_n=F_n-1+F_n-2 for all n>2. Now let S=$\sum_{i=1}^{\infty} 1/F_i$ (for those of you who can't read LaTeX, S = 1/F₁+1/F₂+1/F₃+...). Prove whether S is rational or irrational.

Okay, if it's irrational, an extra dime to prove that it's algebraic xor transcendental. (Well, okay, of course it's one xor the other. But you have to prove which one. ;-) )