# Why does ReplaceAll not work here?

Why does this not change the names of the vertices?

Graph[List[1,2,3], List[UndirectedEdge[1,2], UndirectedEdge[1,3]], List[Rule[VertexLabels,List[Automatic]]]] /. {1->a,2->b,3->c}
(*  the graph =  allConnected[3] *)


The graph is obtained using the code here.

allEdges[n_] :=
Flatten[Table[UndirectedEdge[i, j], {i, 1, n}, {j, i + 1, n}]];
allConnected[n_] :=
Select[Map[Graph[Range[n], #, VertexLabels -> Automatic] &,
Subsets[allEdges[n]]], ConnectedGraphQ];
allConnectedUpToIso[n_] :=
DeleteDuplicates[allConnected[n], IsomorphicGraphQ];


Why does this not work? I want to change the vertice names to my customized names.

I know that I can convert the graph to edge lists and then try the rule (already tried).
I'm curious why it does not work and can we try the rule without converting them to edge lists?

• In order not to make things too complicated, perhaps you could ask your question in a concrete case. For example, why does Graph[List[1,2,3], List[UndirectedEdge[1,2], UndirectedEdge[1,3]], List[Rule[VertexLabels,List[Automatic]]]] /. {1->a,2->b,3->c} not change the names of the vertices? Nov 9, 2022 at 19:13
• I think has to do with fact that Graph transforms to a raw object, similar to sparse arrays, see this answer. I think this question can actually be considered a duplicate of that question, because the answer explicitly mentions Graph. Nov 9, 2022 at 19:24
• Bit of a hack, but this works: ToExpression[ StringReplace[ ToString[InputForm[allConnected[3]]], {"1" -> "a", "2" -> "b", "3" -> "c"}]] Nov 9, 2022 at 19:32
• Following the link in the link above leads to a code in this answer for obtaining the list of functions where presumably replacements do not work : EntityClass["WolframLanguageSymbol", "Atomic"]//EntityList Nov 9, 2022 at 19:51
• Good to know. I have never thought about something that big like Graph can be atomic.
– hana
Nov 9, 2022 at 20:04

You can't use ReplaceAll on a Graph object because it is AtomQ. Use VertexReplace to replace vertices in a Graph.

In your code you would use

VertexReplace[#, {1 -> a, 2 -> b, 3 -> c}] & /@ allConnected[3]