TGViewer
Graph Machine Learning Graph Machine Learning @graphml · 6.59K subscribers
Post #210 1.09K
Easiest unsolved case of reconstruction conjecture

We spent some time thinking about reconstruction conjecture and got into a conclusion that no one yet solved a simple case as follows.

You have a graph composed of two parts X and Y. In X you have n vertices, in Y you have 2 vertices only. Vertices in Y are connected to X such that all vertices in X have degree 5 and all vertices in Y have degree 4.

So final graph has only two values of degrees, 4 and 5. It's know that when a graph is regular, it can be reconstructed. Here there are only 2 vertices of different degree, nonetheless the problem becomes harder. In more general case you have 2 vertices of degree a and n vertices of degree a+1, but it seems to be much harder to reason about.
Telegram Graph Machine Learning Some notes on reconstruction conjecture Studying reconstruction conjecture is going down the rabbit hole 🐇 It seems so simple, but after a few steps its complexity unfolds and you find yourself reading another paper that provides some extra insights which…
More from @graphml
  1. Mar 18, 2026🚀 LOGML 2026 — Mentor Applications Open (Deadline extended!) The LOGML (London Geometry a…
  2. Feb 28, 2026PhD Position in Graph Learning at the University of Vienna, Austria A PhD student position…
  3. Feb 16, 2026Uni Leipzig looking for a motivated student for a PhD position in Graph Machine Learning a…
  4. Oct 2, 2025Tired of evaluating your graph ML models on Cora, CiteSeer, and PubMed? We have a better b…
  5. Oct 2, 2025How can we create general-purpose graph foundation models? (by Dmitry Eremeev) For a long…
  6. Sep 21, 2025GraphML News (September 2025) - Stanford Graph Learning WS, MoML, RF Diffusion 3 While the…
Threads Profile ViewerView any public Threads profile without an account.Open ThreadLook →Writing with AI? Make it sound human.Metric37 rewrites AI drafts so they read naturally. Free AI detector, 1,500 words free.Try Metric37 →