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 yields a not so nice a picture as in your example. It is hard to verify if the answer is correct.

[![enter image description here][1]][1]


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