{"id":464,"date":"2007-07-10T21:53:55","date_gmt":"2007-07-10T21:53:55","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2007\/07\/10\/an-unsolved-simple-graph-problem\/"},"modified":"2007-07-10T21:53:55","modified_gmt":"2007-07-10T21:53:55","slug":"an-unsolved-simple-graph-problem","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2007\/07\/10\/an-unsolved-simple-graph-problem\/","title":{"rendered":"An Unsolved Simple Graph Problem"},"content":{"rendered":"

One of the things that I find fascinating about graph theory is that it’s so simple, and
\nyet, 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.
\nFor 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.<\/p>\n


\nTo state reconstruction formally, we need to define a few terms.
\nSuppose you have a graph G=(V,E). A graph H is called an *induced subgraph* if it’s formed
\nby 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
\nand for all x and y in V’, (x,y)∈E’ if\/f (x,y)∈E.
\nIf 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.
\n\"deck.jpg\"
\nFor 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<\/sub> 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.
\nWith those definitions, now we can state reconstruction properly: Any two graphs G1<\/sub> and G2<\/sub> with more than 2 vertices are isomorphic if and only if they have the same decks.
\nNo 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.
\nThere’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.
\nWe 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.
\nPersonally, 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
\nits subsets of size n-1. (Ok, maybe not *that* obvious, but you get my drift!) But it’s
\nnot – it’s actually deeply non-obvious.<\/p>\n","protected":false},"excerpt":{"rendered":"

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 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[25],"tags":[],"class_list":["post-464","post","type-post","status-publish","format-standard","hentry","category-graph-theory"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-7u","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/464","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=464"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/464\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=464"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=464"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=464"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}