Although we can get a lot done with the graphs already in Sage, most of the time we will need to construct our own. The simplest approach is to modify one of the prebuilt graphs.

For an examples, we start with the circulant graph $G$ on 9 vertices with connection set $C=\{1,2,7,8\}$. So $V(G)=\mathbb{Z}_9$ and vertices $i$ and $j$ are adjacent if their difference is in $C$.

G = graphs.CirculantGraph( 9, [1,2]); G

Circulant graph ([1, 2]): Graph on 9 vertices

For later use we also make a copy of $G$:

H = G.copy()

You can use G.show() to get a view of your graph, this can provide a useful check.

G.show()

We find the neighbors of 0:

G[0]

[8, 1, 2, 7]

and attempt to confirm that $(0,1)$ is an edge by

(0,1) in G.edges()

False

and then realize that we should have tried

(0,1) in G.edges(labels=False)

True

or

G.has_edge(0,1)

True

The last alternative is recommended. We can delete this edge:

G.delete_edge(0,1)

and confirm the effect by

G.degree()

[3, 3, 4, 4, 4, 4, 4, 4, 4]

Note that G.delete_edge() alters $G$ in place, which is why I prepared a copy of it. The copy is unaltered:

H.degree()

[4, 4, 4, 4, 4, 4, 4, 4, 4]

Deleting an edge that is not present has no effect. We can delete the members of a list of edges with

an_edge_list = [(0, 7), (2, 4)]
G.delete_edges( an_edge_list)
G.edges(labels=False)

[(0, 2), (0, 8), (1, 2), (1, 3), 
(1, 8), (2, 3), (3, 4), (3, 5), 
(4, 5), (4, 6), (5, 6), (5, 7), 
(6, 7), (6, 8), (7, 8)]

Similarly we can add an edge or list of edges---type G.add followed by tab to see the things we can add and G.delete followed by tab for the things we can delete (which of course include vertices and list of vertices).

Adding a vertex increases the vertex set but, naturally enough, does not add any edges. If $S$ is a list of vertices of $G$, we can add a new vertex adjacent to each vertex in $S$ as follows.

G.add_edges( [(10,s) for s in [1,2,3]] )
G.edges(labels=False)

[(0, 2), (0, 8), (1, 2), (1, 3), 
(1, 8), (1, 10), (2, 3), (2, 10), 
(3, 4), (3, 5), (3, 10), (4, 5), 
(4, 6), (5, 6), (5, 7), (6, 7), 
(6, 8), (7, 8)]

Here the argument [ (10,s) for s in S ] to G.add_edges() is a simple example of a list comprehension. We will find these are very useful.

Edge contraction is one basic operation in graph theory that is not built into Sage. The following procedure identifies two vertices in a graph.

def contract(H, e):
    G = H.copy() 
    u, v = e[0], e[1]
    vedges = [(v,x) for x in G[u]]  
    G.delete_vertex(u)
    G.add_edges( vedges)
    return G

A useful generalization would be a procedure that took a graph $G$ and a partition of its vertex set as its input, and returned a graph with the cells of the partition as vertices and where two cells are adjacent if there is an edge that joins a vertex in the first cell to a vertex in the second.