Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

alt text

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

alt text

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?

share|improve this question
If you square the new graph with edge subdivisions, you get a disjoint union of your original graph and its line graph. So another way of phrasing the answer below is that the only graphs which are line graphs of their graphs are unions of cycles. –  Gjergji Zaimi Apr 22 '11 at 10:00
add comment

1 Answer

up vote 5 down vote accepted

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.

share|improve this answer
more precisely (1) all graphs not containing a $2$-regular component (a cycle) –  Flo Pfender Apr 22 '11 at 3:14
Thanks, I edited accordingly. –  Tony Huynh Apr 22 '11 at 9:41
Doesn't "graphs not containing a cycle" mean "forests"? –  Hans Stricker Apr 22 '11 at 9:57
There could be some non-associativity of language coming into play here, but I just mean all graphs that do not contain a connected component which is a cycle. –  Tony Huynh Apr 22 '11 at 10:24
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.