Imagine you're designing a road network between cities. You want every city connected, but you also want redundancy — if a few key intersections shut down, traffic should still flow. The number of intersections you can lose before the network splits in two is the network's 'vertex connectivity.' Now here's the twist: in quantum optics, there's a family of entangled states called GHZ states whose dimension — how much quantum information they carry — turns out to be controlled by exactly this kind of connectivity measure, but applied to a colored, weighted graph that represents a photonic experiment. This paper proves, for the first time, a general upper bound on GHZ state dimension in terms of that graph connectivity. The committed claim: for any simple connected GHZ graph G with at least four vertices, the dimension of the GHZ state is at most 2^{κ(G)−1} + C(κ(G), 2), where κ(G) is the vertex connectivity. This is not a computational trick or an approximation — it is a combinatorial proof. The result also extends to edge connectivity and maximum degree. This settles a structural question that has been open since Krenn, Gu, and Zeilinger established the bridge between photonic experiments and edge-colored graphs. The prior art is thin but precise. The Krenn–Gu conjecture says every GHZ graph with more than four vertices has dimension at most 2. Previous work confirmed this for graphs of vertex connectivity ≤ 2 (MFCS 2024) and showed that simple GHZ graphs on n > 4 vertices have dimension less than n/√2 (Quantum 2024). But no one had a general upper bound parametrized by connectivity alone. This paper fills that gap. The bound is exponential in κ(G), so it does not resolve the conjecture outright — but it converts a wide-open structural question into a concrete, attackable inequality. Architecturally, this is pure combinatorial graph theory applied to quantum information. The method belongs to the extremal/structural graph theory family — Menger's theorem, vertex cuts, monochromatic coloring arguments. No quantum hardware, no simulation, no variational circuits. The 'compute' here is mathematical proof, which means the integrity regime is the strongest available: either the proof is correct or it isn't. Peer review via FSTTCS 2026 acceptance is the validation mechanism. The milestone question is sharp. The conjecture says GHZ dimension ≤ 2 for n > 4. This paper proves GHZ dimension ≤ 2^{κ−1} + C(κ, 2). For κ = 2, that's 2 + 1 = 3, which is close but not quite the conjectured 2. For κ = 3, the bound is 4 + 3 = 7. The gap between the proven bound and the conjectured constant 2 is where the action is. Tightening the bound to match the conjecture — or finding a counterexample — is the next concrete goal. The obvious experiment not run: testing whether the bound is tight. Can you construct a GHZ graph with κ = 3 that actually achieves dimension 7? If yes, the conjecture is false and you have a new high-dimensional GHZ construction. If no, the bound is loose and can be tightened. The authors almost certainly explored this computationally, and the absence of a counterexample suggests they couldn't find one — which is circumstantial evidence for the conjecture but not proof. They're likely saving the tightening argument or the computational search results for a follow-up.
