# What is an inductive graph?

My google search turned up much information about what people are doing with inductive graphs, but no definitions. So I ask you, StackExchange, what is an inductive graph? When I think of induction, I think of recursion. But this must be a wrong line of thinking, because cannot all graphs be constructed recursively? Thanks for clearing up my confusion.

-

## 4 Answers

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.

-
So does the set of verticies need to have a partial order? – Athan Clark Jul 5 '14 at 4:11
I think we're talking about numbering the vertices of an $n$-vertex graph with $1,2,3,\dots,n$, each vertex getting a different number. – Gerry Myerson Jul 5 '14 at 4:14
I see. However, the strict ordering is mandatory? Or could you simply limit the total number of edges any vertex has? – Athan Clark Jul 5 '14 at 4:25
If no vertex has degree exceeding $r$, then (no matter how you number the vertices) each vertex has at most $r$ edges to higher-numbered vertices, so the graph is guaranteed to be (trivially) $r$-inductive. The concept "$d$-inductive" would appear to be interesting only if there are vertices of degree bigger than $d$. – Gerry Myerson Jul 5 '14 at 4:28
Another name for this is a $d$-degenerate graph. – Luke Mathieson Apr 8 '15 at 2:08

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.

-
The blog post is fantastic! Thanks for answering the question clearly and linking to the blog for further discussion. – erikprice Dec 23 '15 at 0:01

To be fair, I just used search engines as well. But let me know if either of these ring a bell:

Wikipedia thinks that inductive graphs may also be known as degenerate graphs:

On the other hand, the book The Theory of Graphs defines an inductive graph on page 13:

Do these line up with the sorts of inductive graphs you've been looking at?

-

A graph $G$ is $d$-inductive if either $G$ has at most $d$ vertices or $G$ has a vertex $u$ of degree at most $d$ such that $G \setminus\{ u\}$ is $d$-inductive. Equivalently, $G$ is $d$-inductive if its vertices can be numbered so that at most $d$ neighbors of any vertex $v$ have higher numbers than $v$.

-