Graph()

The command Graph() provides a very useful way to construct graphs. To begin, we will invoke it in the form X = Graph( [vertices, adj_pred] ). There is just one argument, a list consisting of the the vertices is the vertex set of X (itself a list), and a predicate (or function) adj_pred that takes two vertices $u$ and $v$ and returns True or False according as they are adjacent or not.

As a trivial example, we construct the path on 9 vertices:

P9 = Graph([[0..8], lambda i,j: i-j == 1])
P9.edges(labels=False)
[(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8)]

Here lambda is a synonym for "function", its inputs precede the colon and the subsequent text computes its value. By using lambda, we can define our predicate inline. You should experiment to see what happens if you type = in place of ==, since you will eventually do it by accident, and it is good to be able to recognize what's gone wrong. We could have defined the predicate first:

def adj_pred( i,j):
    return i - j == 1



and then created our graph with

P9_2 = Graph([[0..8], adj_pred])
P9_2.is_isomorphic(P9)
True

This illustrates that Python allows us to pass a function as an argument.

Graph() accepts a variety of arguments, including:

  1. A list of edges.
  2. A dictionary of lists.
  3. An adjacency matrix.
  4. A graph6 string.

(For the full list, try Graph??.)

What's a graph6 string? All we need to know is that it is a compact encoding of a graph as an ASCII string. We can produce that string encoding the graph as follows

P9.graph6_string()
'HhCGGC@'

There are other programs (e.g., Brendan McKay's geng) that will produce files of graphs presented as graph6 strings, and so we can read these into Sage and convert them to Sage graphs.

Here is a very natural way to create a graph, by supplying a list of edges.

an_edge_list = [(0,1), (1,2), (2, 3), (3, 0), (1,3)]
G = Graph(an_edge_list)
G.degree()
[2, 3, 2, 3]