FullForm giving misleading answers on Graphs

Question

Let's define a very simple graph, say

And ask for its FullForm:

Great. Except, unlike every other case I've tried FullForm with, this doesn't actually seem to be Mathematica's internal representation of that graph.

Certainly, if I try MatchQ[g, _Graph] I get True. But if I try MatchQ[g, Graph[__], I get False. If I try to replace the head with a List List@@@g, I get the graph back unmodified. If I try to match on and replace one of its internal Lists with g/.List[_]->{c \[UndirectedEdge] d}, I get the graph back unmodified. If I try to rename a vertex with g/.a->x, I get the graph back unmodified.

In short, it seems that the original picture of a graph is somehow closer to being the true internal representation than the FullForm.

I need this because Mathematica's graph manipulation functions are ... incredibly poorly implemented, but that's neither here nor there. I am resorting to manually replacing the list of edges with a new one instead of using EdgeAdd, for example, because EdgeAdd can't handle self-loops and multigraphs (and, after a flurry of not-obviously-related errors, silently crashes the kernel when you try the second time in a session, instead of doing something sane like throwing an exception). Unfortunately, it seems that path is closed as well here, and I'm starting to consider the daunting task of porting the rest of the notebook into something like Python.

Any help would be appreciated. My first thought is to figure out what the "true" FullForm looks like and proceed from there, but it occurs to me that it may also be possible to work around the inability to manually match-and-replace as you can with every other Mathematica object with Graph the way you can swap out property values... though I'm not particularly hopeful.

Answer 1

An expression whose head is Graph evaluates to an atom. The resulting atom also has the head of Graph but only in the sense that the atom 1 has the head Integer. The confusion arises because the composite full-form of the input Graph expression is virtually indistinguishable from the atomic full-form of the output Graph object.

Association suffers from the same problem, as do a growing number of other symbols. Another question ponders the reason behind such behaviour.

Back on StackOverflow, there is a question that asks about Graph in particular and another concerning ways to extract graph properties from the apparent full form instead of using the graph accessor functions.