  Greenberger-Horne-Zeilinger (GHZ) states are quantum states involving at
least three entangled particles. They are of fundamental interest in quantum
information theory, and the construction of such states of high dimension has
various applications in quantum communication and cryptography. They are of
fundamental interest in quantum information theory, and the construction of
such states of high dimension has various applications in quantum communication
and cryptography. Krenn, Gu and Zeilinger discovered a correspondence between a
large class of quantum optical experiments which produce GHZ states and
edge-weighted edge-coloured multi-graphs with some special properties called
the \emph{GHZ graphs}. On such GHZ graphs, a graph parameter called
\emph{dimension} can be defined, which is the same as the dimension of the GHZ
state produced by the corresponding experiment. Krenn and Gu conjectured that
the dimension of any GHZ graph with more than $4$ vertices is at most $2$. An
affirmative resolution of the Krenn-Gu conjecture has implications for quantum
resource theory. On the other hand, the construction of a GHZ graph on a large
number of vertices with a high dimension would lead to breakthrough results.
  In this paper, we study the existence of GHZ graphs from the perspective of
the Krenn-Gu conjecture and show that the conjecture is true for graphs of
vertex connectivity at most 2 and for cubic graphs. We also show that the
minimal counterexample to the conjecture should be $4$-connected. Such
information could be of great help in the search for GHZ graphs using existing
tools like PyTheus. While the impact of the work is in quantum physics, the
techniques in this paper are purely combinatorial, and no background in quantum
physics is required to understand them.
