Jenny Kenkel, Grinnell College
Jenny Kenkel
Grinnell College
The Graph Reconstruction Conjecture
Join this talk via Zoom: Click to join
A graph is a collection of vertices that are connected with edges. Graphs are used in modelling social networks, flights, links on websites, and in a host of other areas. A card of a graph is defined to be the smaller graph formed by deleting a single vertex and all edges connected to that vertex. The deck of the graph is defined to be the collection, possibly with repeats, of cards of the graph. The Graph Reconstruction Conjecture, by Kelly and Ulam, is a decades old open question: is it always possible to figure out the original graph by looking at its deck? In this talk, we will practice reconstructing some graphs, determine which properties of graphs can be reconstructed, and explore what makes this question so hard.
Feel free to share!
