Reconstructing a Graph from the Incidence Relation on its Edge Set
Bohdan Zelinka · Czech digital mathematics library · 1972
We consider a connected undirected graph G without loops and multiple edges.Our goal is to reconstruct G if we know its edge set E and the relation o of incidence on this set.(This means that (e±, e 2 ) e Q, where e\eE, e 2 eE, if and only if the edges e±, e 2 have a common end vertex.)We suppose that G has at least two edges; the reverse case is trivial.The theorem of Whitney [2] asserts that this reconstruction is possible for any finite graph without loops and multiple edges which is not isomorphic to any of the graphs in Fig. 1.