example

var graph = new ImmutableGraph();
var graph1 = graph.addVertex( 2 )
var graph2 = graph1.addVertex( 1 );

var graph3 = graph2.addEdge( "A", [ 1, 2 ] );

immutable-graph.js

// Using Immutable.js - https://github.com/facebook/immutable-js

function ImmutableGraph( vertices, edges, vertexMap, edgeMap ) {
    this.vertices = Immutable.Set.from( vertices );
    this.edges = Immutable.Set.from( edges );

    this.vertexMap = Immutable.Map.from( vertexMap );
    this.edgeMap = Immutable.Map.from( edgeMap );
}

ImmutableGraph.prototype.addVertex = function( vertex ) {
    return new ImmutableGraph(
        this.vertices.add( vertex ),
        this.edges,
        this.vertexMap.set( vertex, Immutable.Vector() ),
        this.edgeMap
    );
};

ImmutableGraph.prototype.addEdge = function( edge, vertices ) {
    return new ImmutableGraph(
        this.vertices,
        this.edges.add( edge ),
        this.vertexMap.withMutations( function( map ) {
            for ( var i = 0; i < vertices.length; i ++ ) {
                map.set( vertices[ i ], map.get( vertices[ i ] ).push( edge ) );
            }
        } ),
        this.edgeMap.set( edge, Immutable.Vector.from( vertices ) )
    );
};