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][1]][1]


  [1]: http://i.stack.imgur.com/iTWCb.jpg