EdgeAdd function not adding edges to a RandomGraph[ ] with no edges

Question

Bug introduced in 9.0 or earlier, fixed in 11.3

---

I have a graph:

g = RandomGraph[{1, 0}]

So basically, it is just one vertex. I want to add some vertices and edges in the following steps so i tried this first to add a new vertex:

g = VertexAdd[g, VertexCount[g] + 1];

Since the vertex names are just numbers, I added the next unused integer. I want my g graph to be updated (have a new vertex added to it) to the new state so I used the = operator.

Then I tried to add an edge between those by using the EdgeAdd function:

g = EdgeAdd[g, {1\[UndirectedEdge]2}]

And the output is just:

EdgeAdd[, 2<->3]

Why is it not working? Is it some kind of bug or am i using something wrong here?

Answer 1

Perhaps it's a nuisance (bug?) of RandomGraph[ ]. Here is a way to force it:

g = Graph[VertexList@#, EdgeList@#] &@RandomGraph[{1, 0}];
g1 = VertexAdd[g, 2];
g2 = EdgeAdd[g1, UndirectedEdge[1, 2]]

Answer 2

There are several Graph-related bugs that show up only for certain graphs, most likely due to how these graphs are stored internally. There are several possible internal graph representations used by Mathematica.

When you find that something like this happens, try recreating the graph in one of several possible ways:

g = Uncompress@Compress[g]

will preserve all properties.

g = Graph[VertexList[g], EdgeList[g]]

works but discards properties.

g = GraphComputation`ToGraphRepresentation[g, "Incidence"]

may work too if the graph is not empty (i.e. has more than zero vertices).

Answer 3

If you don't mind messing with System` symbols, you can unprotect EdgeAdd, and incorporate @Szabolcs's workaround. Here is an attempt to do so:

$BugFix=True;
Protect[$BugFix];

Unprotect[EdgeAdd];
Clear[EdgeAdd];
EdgeAdd[g_, e___] /; $BugFix := Block[{$BugFix = False},
    Module[{res},
        res = Quiet @ Check[EdgeAdd[g,e], $Failed];
        (
            Replace[res, _EdgeAdd :> EdgeAdd[Uncompress@Compress@g, e]]
        ) /; res=!=$Failed
    ]
]
Protect[EdgeAdd];

A couple examples:

EdgeAdd[ GraphComplement[CompleteGraph[5]], 1 <-> 2 ]
EdgeAdd[ RandomGraph[{1, 0}], 1 <-> 2 ]