GraphJoin

<< DiscreteMath`Combinatorica`

The graph g has all its vertices rendered as larger than normal boxes. The graph h has its vertices rendered as larger than normal disks. The join of the two graphs has the correct set of vertices and edges, but all vertices end up inheriting the property of being rendered as large big boxes. Some people may consider this correct behavior, but this behavior violates the semantics that objects in each graph will keep as many of their graphics properties intact as possible during a graph operation,

g  =  
      SetGraphOptions[
        Cycle[4],  {{{1,  2},  {2,  3},  EdgeStyle -> Thick,  
            EdgeColor -> Red}},  
        VertexStyle ->  Box[Large]]

ShowGraph[g]

h =  
      SetGraphOptions[
        Star[4],  {{1,  4},  {2, 4},  EdgeStyle -> Thick,  
          EdgeColor -> Green},  
        VertexStyle -> Disk[Large]]

ShowGraph[h,  VertexNumber -> True]

ShowGraph[GraphJoin[g,  h]]