Question

Consider an undirected graph. It's obvious what is a vertex (≙ object) and what is an edge (≙ fact).

Now "objectify" the edges (≙ facts) by adding an extra vertex along every edge.

In general, in the "(edge-)objectified" graph it's not determined anymore which vertices correspond to "objects" and which vertices correspond to "facts", e.g. in objectified cycle graphs. But sometimes it is, e.g. in objectified path or star graphs.

In the case of cycle graphs, the objectified graph can nevertheless be "un-objectified" uniquely.

How can graphs be characterized

1. for which "objects" and "facts" can be distinguished in their "objectified" graph (like in path and star graphs)

2. that can be "un-objectified" uniquely (like cycle graphs)

Where can I learn more about this approach? Under which term is it filed?

Answer 1

If I understand your questions correctly, I think the answer to (1) is all graphs not containing a cycle as a component, and the answer to (2) is all graphs.

Let $G'$ be the graph obtained from a connected graph $G$ by subdividing each edge once. Note that $G'$ is bipartite and has a bipartition $(A,B)$ where each vertex in $A$ has degree 2. If $B$ has a vertex of degree not equal to 2, then the vertices in $B$ correspond to the vertices of $G$, and so we can recover $G$ from $G'$. Otherwise, $|A|=|B|$ and $G'$ is a cycle. In the second case we can still recover $G$ from $G'$, but cannot distinguish objects and facts.