What is an inductive graph?

Apart from the graph-theoretical answer, "inductive graph" has another meaning in functional programming, most notably Haskell. It's a functional representation of a graph that allows operations similar to standard inductive data types (ie lists and trees), useful for writing graph algorithms in a functional style. The idea was introduced by Martin Erwig in "Inductive Graphs and Functional Graph Algorithms" and reified in his functional graph library (fgl).

In this context, an "inductive data type" is one like a list or tree that is built up in a unique way. Since there is only one way to construct a particular list or tree, there is a single way to pattern match on it as well. Graphs, however, do not have a natural ordering of nodes or edges, and so are not inductive. (The actual structure storing the graph is just an implementation detail.)

The core concept with inductive graphs is that we can view a graph as an inductive data type, even though it was not built up this way. We can pattern match on a graph and decompose it into a single node, its vertices and the rest of the graph. However, since graphs are not inductive, there is more than one valid way to decompose a graph like this, so we lose the canonicity of actual inductive data types. This is primarily solved by parameterizing the viewing function with a specific node, letting us direct our graph decomposition as we go along.

If you want a more descriptive introduction—with pictures!—you can read a post I wrote about the idea on my blog.

Inductive graphs are efficiently implemented in terms of a persistent tree map between node ids (ints) and labels, based on big-endian patricia trees. This allows efficient operations on the immutable base, letting inductive graphs behave much like any other immutable, persistent data structure.

A graph $G$ is $d$-inductive if the vertices of $G$ can be numbered so that each vertex has at most $d$ edges to higher-numbered vertices.