3 of 5 deleted 5 characters in body

I have used the functions EdgeDelete and EdgeAdd to expand the graph. The code generates new vertex names by incrementing the largest vertex name in the graph.

nextVertexNames[g_] := Max[VertexList[g]] + {{1, 2, 3}, {4, 5, 6}}
replaceTripod[g_, v_] := Module[{
   oldNeighbors = DeleteCases[VertexComponent[g, v, 1], v], 
   newNeighbors = nextVertexNames[g], go = g
   },
  EdgeAdd[
   EdgeDelete[go, v <-> _],
   Flatten@{
     UndirectedEdge[v, #] & /@ First[newNeighbors],
     UndirectedEdge @@@ Partition[Riffle @@ newNeighbors, {2}, 1, 1],
     UndirectedEdge @@@ Thread[{Last@newNeighbors, oldNeighbors}]}
   ]
  ]
replaceTripods[g_] := 
  Fold[replaceTripod, g, 
   Extract[VertexList[g], Position[VertexDegree[g], 3]]];

For your case, use replaceTripods[g] to replace all tripods in the graph g.

This does not yield the nice picture as in your example. It is therefore hard to verify if the answer is correct by looking at it.

enter image description here