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:

- A list of edges.
- A dictionary of lists.
- An adjacency matrix.
- 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]