Why equivalent Graph objects yield different results?

Question

Bug introduced in 10.0 or earlier and fixed in 12.0.

---

I am working with Mma 11.2 for win 7. I am confusing about the results returned by ConnectedGraphQ described as follows:

Mma believe that Graph[{1}, {}] and Graph[{1, 1}, {}] are the same:

Graph[{1}, {}] === Graph[{1, 1}, {}]

True

However, different results are yeilded:

ConnectedGraphQ[Graph[{1}, {}]]

True

ConnectedGraphQ[Graph[{1, 1}, {}]]

False

Tracing back, one can find:

ConnectedGraphQ[Graph[{1}, {}]] // Trace // InputForm

{{HoldForm[Graph[{1}, {}]], HoldForm[Graph[{1}, {}]]}, HoldForm[ConnectedGraphQ[Graph[{1}, {}]]], HoldForm[True]}

ConnectedGraphQ[Graph[{1, 1}, {}]] // Trace // InputForm

{{HoldForm[Graph[{1, 1}, {}]], HoldForm[Graph[{1}, {}]]}, HoldForm[ConnectedGraphQ[Graph[{1}, {}]]], HoldForm[False]}

What's wrong?

Answer 1

I think you've stumbled upon a side-effect of Graph objects being "stateful". They're legit objects, which we can get a glimpse of in their atomiticity:

g1 = Graph[{1}, {}];
g2 = Graph[{1, 1}, {}];
g3 = FirstCase[ToExpression@ToBoxes@g1, _Graph, None, \[Infinity]];
g4 = FirstCase[ToExpression@ToBoxes@g2, _Graph, None, \[Infinity]];
g1 === g2 === g3 === g4

True

Quiet[Check[g2[[1]], $Failed, Part::partd]]

$Failed

And of course there's the fact that the reported expression structure doesn't actually correspond to the internal structure.

Here's a cool rundown of all these Qs on these different Graph objects:

gfuncs =
  {GraphQ, PathGraphQ, TreeGraphQ, MixedGraphQ, PlanarGraphQ, 
   SimpleGraphQ, AcyclicGraphQ, CompleteGraphQ, DirectedGraphQ, 
   EulerianGraphQ, LoopFreeGraphQ, WeightedGraphQ, ConnectedGraphQ, 
   IsomorphicGraphQ, UndirectedGraphQ, HamiltonianGraphQ, 
   WeaklyConnectedGraphQ};
Prepend[Through[gfuncs[#]] & /@ {g1, g2, g3, g4}, gfuncs] // 
  Transpose // NewlineateInput

{
 {GraphQ, True, True, True, True},
 {PathGraphQ, True, True, True, True},
 {TreeGraphQ, True, True, True, True},
 {MixedGraphQ, False, False, False, False},
 {PlanarGraphQ, True, True, True, True},
 {SimpleGraphQ, True, True, True, True},
 {AcyclicGraphQ, True, True, True, True},
 {CompleteGraphQ, True, True, True, True},
 {DirectedGraphQ, True, True, True, True},
 {EulerianGraphQ, True, True, True, True},
 {LoopFreeGraphQ, True, True, True, True},
 {WeightedGraphQ, False, False, False, False},
 {ConnectedGraphQ, True, False, True, False},
 {IsomorphicGraphQ, True, True, True, True},
 {UndirectedGraphQ, True, True, True, True},
 {HamiltonianGraphQ, True, True, True, True},
 {WeaklyConnectedGraphQ, True, True, True, True}
 }

We can see that, for whatever reason, only ConnectedGraphQ shows this behavior.

The fact that g4 has the same behavior as g1 is very odd. It might have to do with the memory sharing of that core Expression object, but that's just errant speculation

Answer 2

These sorts of bugs can often be worked around by cycling the graph through its compound expression representation, like here.

badGraph = Graph[{1, 1}, {}];

ConnectedGraphQ[badGraph]
(* False *)

ConnectedGraphQ@Uncompress@Compress[badGraph]
(* True *)

---

Graph is atomic and its actual internal representation is not the same what you see when you apply InputForm to it. This is why two seemingly identical graphs can behave differently. As I understand, all atomic expressions also have a compound representation, which is used in some contexts. Converting to this and back forces re-creating the internal representation, which will often fix problems like this.

I am aware of several similar Graph-bugs related to a broken internal representation. Sometimes the breakage is such that it is reflected in the input form, like here, and sometimes it isn't, as in your case. Cycling the graph fixes it only in the latter case.

---

The simplest practical fix to this problem is defining your own function:

connectedGraphQ[g_?GraphQ /; VertexCount[g] == 1] := True
connectedGraphQ[g_] := ConnectedGraphQ[g]

IGConnectedQ from IGraph/M also works, but I would not recommend it in this specific case as it will be much slower than ConnectedGraphQ on tiny graphs due to the conversion overhead.