Fredrick wrote approximately:

> $J : \textbf{Graph} \rightarrow \mathbb{N}^\mathbb{N}$

> Does \$$J\$$ have an inverse? Does \$$J\$$ have a right adjoint?

(Here \$$\mathbb{N}^\mathbb{N} \$$ is my preferred notation for the set of functions from \$$\mathbb{N}\$$ to itself - that is, sequences of natural numbers

This is a great thing to think about. The questions as stated don't make sense, for two reasons. Both these problems can be fixed:

A. It is not a graph that gives a sequence of numbers, but a **pointed graph**: a graph with a chosen node. This lets us count the number of paths of length \$$n\$$ starting and ending at that node, and get a sequence of natural numbers. There is a category \$$\textbf{Graph}_\ast\$$ of pointed graphs, where a morphism is a map of graphs that sends the chosen node of one to the chosen node of the other.

B. \$$\textbf{Graph}\_\ast \$$ is a _category_ while \$$\mathbb{N}^\mathbb{N} \$$ is a mere _set_. Thus, it's not clear what \$$J\$$ should be: a functor (a map between categories) or a function (a map between sets). We can cure this problem in two equivalent ways:

1. Turn the category \$$\textbf{Graph}_\ast \$$ into a set, namely the set of isomorphism classes of pointed graphs.

2. Turn the set \$$\mathbb{N}^\mathbb{N} \$$ into a category with only identity morphisms.

Since they're equivalent we can use the first, less stressful approach.

There is indeed a well-defined function \$$J\$$ from the set of isomorphism classes of pointed graphs to the set of sequences of natural numbers, where we count the number of paths of length \$$n\$$ from the chosen node to itself.

This function \$$J\$$ is neither one-to-one nor onto. The interesting question are thus:

1. Which sequences of natural numbers arise by counting the number of paths of length \$$n\$$ from the chosen node in a pointed graph to itself?

1. When do two pointed graphs give the same sequence?

I know a nice answer to the first, which I'll explain if nobody can guess it, but I'm pretty clueless about the second.

I think Matthew Doty at least can guess the answer to the first question here, since he rapidly translated the Pell sequence into a pointed graph that gives it.

I think the easiest way to tackle the first question is to figure out a nice general formula for the number of paths of length \$$n\$$ from any node in a graph to any other node.