Let 𝐺 be an undirected connected graph in which every edge has a positive…

Final answer: In each cycle in G, either all edges have even weight or all edges have odd weight. This is the only statement that must hold for every such graph.

Proof:

• Work modulo 2: replace each edge weight by its parity (0 for even, 1 for odd). The hypothesis says every spanning tree has total parity 0.

• Fix any cycle C and pick two edges e and f in C. Remove e from the cycle to obtain a path; extend that path to a spanning tree T of G that contains all edges of C except e.

• Edge f belongs to T while e does not. Replacing f by e in T gives another spanning tree T'. Parity(T') ≡ Parity(T) + parity(e) + parity(f) (mod 2). Since both trees must have parity 0, parity(e) ≡ parity(f).

• Therefore every pair of edges in C have the same parity, so C is either all-even or all-odd. This proves the asserted statement.

Counterexamples showing the other statements can fail:

• Not all edges must be even: a triangle with weights 1,1,1 has each spanning tree weight 2 (even), yet the edges are odd.

• It is not necessary that all edges are globally all-even or all-odd: a tree with edge weights 1,2,1 has its unique spanning tree weight 4 (even), but edges have mixed parity.

• Not every cycle must be all-even: the triangle with weights 1,1,1 again shows a cycle can be all-odd while the spanning-tree condition holds.