I’ve just come across this web page, which has some puzzles regarding infinite graphs. I’ve solved the first ten, and they’re nice. Some examples include:
- Describe all graphs with a countably infinite number of nodes such that every vertex has degree two.
- If possible, describe a graph with a unique vertex of every degree.
The first one is easier, IMO. If anyone’s curious, I can write up my solutions to all ten problems in another post.
Anyway, I found this page because I was looking for information about infinite graphs in general, which I’m interested in because of a new graph-representation schema I’ve come up with. Everybody knows the two standard representations:
- Keep a list of nodes and a list of edges.
- Keep track of a square matrix whose entry at (r, c) is 1 if node r is connected to node c and 0 if it isn’t.
But these only work for finite graphs, and I started wondering if there was a representation that would work for infinite graphs too.
The first idea I came up with was to represent a graph as an algorithm whose input is the name of a node and whose output is a list of nodes that are adjacent to it. Actually, this representation has an issue where if a node N has an infinite number of neighbors, then you can’t stuff them all into a list on a computer with finite memory. But you can get around this by instead returning an iterator — an object that you can keep calling .next() on and it keeps computing and returning the next element of an infinite sequence. Folks on the functional-programming side of the aisle can think of the neighbor-finding algorithm as returning another algorithm, whose input is an integer k and whose output is the kth neighbor of the original node N.
The other idea I had is to represent a graph as an algorithm whose input is the names of two nodes, and whose output is 1 if the nodes are connected and 0 if they aren’t.
Of course, both of these representations only work for graphs with a countable number of nodes, since the finite-sized inputs to a computer algorithm can’t encode a choice among an uncountable number of options. (Obviously in practice you will only ever inspect a finite portion of any graph. But you can still represent the whole thing as long as it’s countable, and as long as you consider “this algorithm would compute the right answer for any of the infinitely many inputs, if only I had time to try them all” as an acceptable form of representation.)
But more interestingly, I’m wondering what the limitations of this schema are. There are certainly some countable graphs you still can’t represent, such as the graph whose nodes are integers and whose edges only connect consecutive Busy Beaver numbers, which famously can’t be computed by any algorithm. But before I can investigate what sorts of infinite graphs can’t be represented by this algorithm, I need to investigate what sorts of infinite graphs exist — hence, my interest in infinite graphs.
PS: I realized while editing this post that my suggested graph actually can be represented by my schema. Simply connect all positive even numbers in an infinite chain and leave every other node isolated (eg, no neighbors). This has a different labeling of nodes than the Busy-Beaver graph, but the two are isomorphic to each other. Since I’m currently only interested in representing unlabeled graphs, this means the two are identical in my eyes. But here’s one that doesn’t suffer from the issue: let K(n) be the fully-connected graph with n vertices and let B(n) be the nth busy-beaver number. Then the union over all integers i of K(B(i)) is an graph that can’t be represented by any algorithm.