The Stack Overflow podcast is back! Listen to an interview with our new CEO.
4 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. Some vertices seem to have more then 3 edges (for instance 1). You can check however with VertexDegree that all vertices have indeed 3 edges.

enter image description here