# Edge-objectified graphs

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)

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.
• more precisely (1) all graphs not containing a $2$-regular component (a cycle) – Flo Pfender Apr 22 '11 at 3:14