One of the things that I find fascinating about graph theory is that it’s so simple, and
yet, it’s got so much depth. Even when we’re dealing with the simplest form of a graph – undirected graphs with no 1-cycles, there are questions that *seem* like that should be obvious, but which we don’t know the answer to.
For example, there’s something called the *reconstruction theorem*. We strongly suspect that it’s really a theorem, but it remains unproven. What it says is a very precise formal version of the idea that a graph is really fully defined by a canonical collection of its subgraphs.
To state reconstruction formally, we need to define a few terms.
Suppose you have a graph G=(V,E). A graph H is called an *induced subgraph* if it’s formed
by deleting some vertices from G, but keeping all of Gs edges between undeleted vertices. More formally, H=(V’,E’) is a induced subgraph of G=(V,E) if and only if V’⊂V
and for all x and y in V’, (x,y)∈E’ if/f (x,y)∈E.
If H is an induced subgraph of G formed by deleting *exactly one* vertex from G, then H is called a *vertex deleted induced subgraph* of G.
For a graph G, the *deck* of G is the *bag* of all vertex deleted subgraphs of G. (A bag is a set which can contain a single value multiple times. Since it’s possible for a graph to have multiple vertex deleted induced subgraphs that are isomorphic, the deck must be a bag, not a set. For example, K5 has 5 isomorphic vertex deleted subgraphs; it might be possible for there to be a *different* graph with only 4.) An example of a graph and its deck is in the figure to the right.
With those definitions, now we can state reconstruction properly: Any two graphs G1 and G2 with more than 2 vertices are isomorphic if and only if they have the same decks.
No one knows for sure if the reconstruction theorem is actually true. We do know for certain that it’s true for every possible graph with less than 12 vertices. In fact, for graphs with less than 12 vertices, we know something even stronger: that any two graphs with the same *sets* of vertex induced subgraphs are isomorphic. The reason we know this is because someone used a computer to exhaustively generate all possible graphs with less than 12 vertices.
There’s also a probabilistic proof that reconstruction is true for *almost* all graphs: the probability of a randomly generated graph with N vertices being a counterexample to reconstruction approaches 0 as N approaches infinity. But we don’t know if that probability is every greater than 0 – just that it must approach 0 as graphs get larger.
We even know that reconstruction is *not* true for directed graphs. But even with all of this, we just don’t know if it’s really a theorem.
Personally, I find that remarkable. It seems like reconstruction should be *obvious* – as obvious as, say, the fact that a set of size N can be wholly determined by the set of
its subsets of size n-1. (Ok, maybe not *that* obvious, but you get my drift!) But it’s
not – it’s actually deeply non-obvious.
I love those simple-to-state but difficult to prove conjectures. I hadn’t seen this one before.
It reminds me a little of Frankl’s Conjecture which is also combinatoric in flavour and seems intuitively true. It’s also, surprisingly, an open problem.
I wonder if the two are related. Can we map decks to union-closed families of sets?
Nice post! Thanks.
Somewhat off topic, but the illustrations you’ve been including in this series of posts on graph theory are nice and very helpful. I was wondering which software package you’re using to create them.
There are so many interesting questions in graph theory! I’ve never heard of this one, but you’re right–it seems absolutely obvious. Funny how the most obvious things can often turn out to be very difficult to prove (or even be false!)
No one knows for sure if the reconstruction theorem is actually true. Surely that makes it a conjecture, not a theorem? I’m no mathematician, but I thought the distinction between “proved” and “not proved” was rather fundamental in formal mathematics, and that “not yet proved but we think it’s true” didn’t count as “proved”.
It is obviously FALSE for infinite graphs. So restrict the problem to finite cases.
Consider an infinite tree with an infinite vertex degree at each vertex and (to make this simple) “infinite” means countably infinite.
The infinite bag of subtrees are each the same as the tree from which we started.
But, hello! From an infinite set of infinite trees with an infinite vertex degree at each vertex, I can’t tell if I started with one tree, or an infinite forest of trees.
Even the finite case is very wierd, but I’ll save that for another comment. I’ve been grading hideously bad homeworks for about 12 hours now…
Kurt:
I’m using OmniGraffle on a mac. It’s a really wonderful little package – one of the best pieces of software I’ve ever used: it’s an extremely powerful flexible drawing package with a simple, clear UI.
MCC wrote: “One of the things that I find fascinating about graph theory is that it’s so simple, and yet, it’s got so much depth.”
You’d get along well with my thesis advisor. If he’s talking to a student about mathematics and the beauty of it, he’ll almost always talk about the four-color problem as a perfect example of a seemingly simple problem with incredible complexity built in.
What’s bizarre about this not being proved nor disproved is that it is equivaloent to an apparrently very simple question about 0-1 matrices.
Consider the incidence matrix of the graph G. If V(G) = number of verticies of G = n, then the matrix is an nxn matrix, with M[i,j] = 0 if there’s no edge connecting V[i] and V[j], and M[i,j] = 1 if there’s an edge connecting V[i] and V[j].
Our set of induced subgraphs is equivalent to a set on n submatrices, each (n-1)x(n-1), where one row and column have been deleted (if V[i] deleted, then row[i] and Column[i] are deleted).
If we can reconstruct M from {induced subgraphs of M} then ALL the information in the matrix is contained in the submatrices.
Alternatively, if we can NOT reconstruct M from {induced subgraphs of M} then, there is some sort of spooky GLOBAL INFORMATION which is somehow in M as a whole but not in its (n-1)x(n-1) submatrices.
It should, my intuition told me at age 18, be OBVIOUS which case is the fact. But it is anything but obvious.
Where is the information hiding? Or is it all in plain sight?
Seems like such a simple question.
So — are we stupid, or merely ignorant?
No hope if the former. We can learn, if the latter.
I think you know what I believe here.
Great problem, isn’t it?
I studied graphs theory both undergrad and grad so, don’t feel there’s no love out there.
‘specially graph grammars.
I once made a world for a game that was a dodecahedron with Petersen graphs on the faces except at the poles, which had Groetsch graphs. Very hard to get around!
I guess the trickiness of the reconstruction is due to the fact that removing a vertex loses information. That is, it is possible to conceive of graphs such that the removal of two different vertices results in two isomorphic subgraphs (this is why, as Mark CC points out, a bag of subgraphs is required). The missing information in this case is which subgraph goes with which vertex.
You can also see this in the adjacency matrix formulation. Removing one row+column from the matrix can lead to the same submatrix as removing a different row+column. I think the “spooky global information” Jonathan refers to is this mapping from vertex to subgraph or row+column to submatrix.