Representing Graphs

We define a graph to be a set of vertices with a set of pairs of these vertices called edges. The representation of graphs takes on different requirements depending upon whether the intended consumer is a person or a machine. Computers digest graphs best as data structures such as adjacency matrices or lists. People prefer a visualization of the structure as a collection of points connected by lines, which implies adding geometric information to the graph.

In the complete graph on five vertices, denoted K_5, each vertex is adjacent to all other vertices. CompleteGraph[n] constructs the complete graph on n vertices.

ShowGraph[ CompleteGraph[5] ];

The adjacency matrix of K_5 shows that each vertex is adjacent to all other vertices. The main diagonal consists of zeros, since there are no self­loops in the complete graph, meaning edges from a vertex to itself.

TableForm[ Edges[CompleteGraph[5]] ]

The standard embedding of K_5 consists of five vertices equally spaced on a circle.

Vertices[ CompleteGraph[5] ]

The number of vertices in a graph is termed the order of the graph.

V[ CompleteGraph[5] ]

With an optional argument to specify whether we count directed or undirected edges, M returns the number of edges in a graph.

{M[CompleteGraph[5]], M[CompleteGraph[5], Directed]}

A star is a tree with one vertex of degree n - 1. Adding any new edge to a star produces a cycle of length 3.

ShowGraph[ AddEdge[Star[10], {1,2}] ];

The adjacency list representation of a graph consists of n lists, one list for each vertex v_i, 1 <= i <= n, which records the vertices v_i is adjacent to. Each vertex in the complete graph is adjacent to all other vertices.

TableForm[ ToAdjacencyLists[CompleteGraph[5]] ]

There are n (n - 1) ordered pairs of edges defined by a complete graph of order n.

ToOrderedPairs[ CompleteGraph[5] ]

An induced subgraph of a graph G is a subset of the vertices of G together with any edges whose endpoints are both in this subset. An induced subgraph that is complete is called a clique. Any subset of the vertices in a complete graph defines a clique.

ShowGraph[ InduceSubgraph[CompleteGraph[20],
RandomSubset[Range[20]]] ];

The vertices of a bipartite graph have the property that they can be partitioned into two sets such that no edge connects two vertices of the same set. Contracting an edge in a bipartite graph can ruin its bipartiteness.

ShowGraph[ Contract[ CompleteGraph[6,6],{1,7} ] ];

A breadth­first search of a graph explores all the vertices adjacent to the current vertex before moving on. A breadth­first traversal of a simple cycle alternates sides as it wraps around the cycle.


In a depth­first search, the children of the first son of a vertex are explored before visiting his brothers. The depth­first traversal differs from the breadth­first traversal above, proceeding directly around the cycle.

DepthFirstTraversal[Cycle[20], 1]

Different drawings or embeddings of a graph can reveal different aspects of its structure. The default embedding for a grid graph is a ranked embedding from all the vertices on one side. Ranking from the center vertex yields a different but interesting drawing.


The radial embedding of a tree is guaranteed to be planar, but radial embeddings can be used with any graph. Here we see a radial embedding of a random labeled tree.

ShowGraph[ RandomTree[10] ];

An interesting general heuristic for drawing graphs models the graph as a system of springs and lets Hooke's law space the vertices. Here it does a good job illustrating the join operation, where each vertex of K_7 is connected to each of two disconnected vertices. In achieving the minimum energy configuration, these two vertices end up on different sides of K_7.

GraphJoin[EmptyGraph[2], CompleteGraph[7]]]];


Combinatorica functions for representing graphs.