Can Every Combinatorial Graph Be Proven to Correspond to a Topological Space?

[Oxymoron]

I've read (and I've been told in lectures) that each graph (let's just say a combinatorial graph) corresponds to a topological space called the geometric realization - in this space the vertices are distinct points and the edges are subspaces homeomorphic to [0,1]. My question is this: Is this provable? I mean, lots of book say this but I'm not entirely convinced. This is probably easy to prove but I have not seen it anywhere. If someone could show me, or instruct me, or provide a link, or something, I would be very happy!

 

[Hurkyl]

It's rather straight-forward. (at least if you know about quotient spaces)

(1) Choose an orientation for each edge.
(2) Take a copy of [0, 1] for every edge, and a copy of * (the one-point space) for every vertex.
(3) Glue vertices to edges where appropriate.

 

[shmoe]

You can also stick your graph in R^n. If you have n vertices, set them at the points (1,0,...0),(0,1,0,...0),...(0,0,...,0,1) and connect with straight lines the vertices that have edges between them (there will be no intersections). Take the topology inhereted from R^n, the edges will be homeomorphic to [0,1] like you wanted.

 

[Oxymoron]

Thankyou both for replying. It was unexpected as I could not find many references on the internet about this sort of thing. Perhaps you guys might know of some books or websites about Graphs and their actions on Trees.

Posted by Hurkyl

It's rather straight-forward. (at least if you know about quotient spaces)

(1) Choose an orientation for each edge.
(2) Take a copy of [0, 1] for every edge, and a copy of * (the one-point space) for every vertex.
(3) Glue vertices to edges where appropriate.

...and this works for every possible graph I can think of? Why must each edge have an orientation? I am trying to justify each of these three steps. Is it true that every graph admits an orientation? What if I don't orient the edges, will this still work?

Posted by Shmoe

You can also stick your graph in R^n. If you have n vertices, set them at the points (1,0,...0),(0,1,0,...0),...(0,0,...,0,1) and connect with straight lines the vertices that have edges between them (there will be no intersections). Take the topology inhereted from R^n, the edges will be homeomorphic to [0,1] like you wanted.

At the risk of sounding rude; how do you "stick" a graph in R^n? I guess I need a little more explanation, like how do you know that the edges will be homeomorphic to [0,1]? Is it simply because of the inhereted topology on R^n?

 

[shmoe]

The only graph theory book I've ever used was West, "Introduction to Graph Theory". It seemed good, but I have no comparison.

..and this works for every possible graph I can think of? Why must each edge have an orientation? I am trying to justify each of these three steps. Is it true that every graph admits an orientation? What if I don't orient the edges, will this still work?

The orientation was just so you could call one end "0" and the other end "1". You choice of which end of an edge to call 0 is arbitrary.

At the risk of sounding rude; how do you "stick" a graph in R^n? I guess I need a little more explanation, like how do you know that the edges will be homeomorphic to [0,1]? Is it simply because of the inhereted topology on R^n?

Just order the vertices any way you like, identify them with the points I gave. The edges will be finite straight line segments, like from (1,0,0,...,0) to (0,1,0,...,0), it's obvious this is homeomorphic to [0,1], no? You can find an explicit homeomorphism without trouble if you like.

 

[Oxymoron]

I need to ask a quick question which is a little off topic:

I had a graph $\Gamma$ and defined a function $d\,:\,V(\Gamma) \times V(\Gamma) \rightarrow \mathbb{N}$ as being the number $d(P,Q)$ - the minimal path length in the graph with origin P and terminus Q. Then I want to show that this is a metric. So I would have to show

1. $$d(P,Q) \geq 0$$

2. $$d(P,Q) = 0 \Leftrightarrow P=Q$$

3. $$d(P,Q) = d(Q,P)$$

4. $$d(P,Q) \leq d(P,R) + d(R,Q)$$.

For (1.) I said since path length is never negative, the minimum path length is never negative. Is that enough?

For (2.) I said if P=Q then there is no path between them hence the path length is 0, and conversely if d(P,Q) = 0 then there is no path and hence the vertices are the same, i.e. P=Q.

For (3.) I said suppose $d(P,Q) \neq d(Q,P)$ then there exists two paths (one from P to Q and one from Q to P) with different path lengths. If d(P,Q) is minimal then there cannot exist a shorter path. Hence $d(P,Q) \neq d(Q,P)$ is contradictory. Therefore d(P,Q) = d(Q,P). Does this sound ok, honestly I don't like it.

For (4.)...well...I tried treating it like any other Triangle inequality proof but I got stuck. Consider the path from P to Q. Then d(P,Q) is the minimal path length. The way I understand it, there could be many, many different paths between P and Q, but d(P,Q) picks the shortest one and returns a natural number. Now, what if the vertex R is somewhere along this shortest path? Then surely $d(P,Q) = d(P,R) + d(Q,R)$, yes? Well, surely that is ok?

 

[Oxymoron]

What is the one-point space?

 

[Oxymoron]

I have concluded that not every graph can be recovered from its geometric realization. Before I go on, does anyone else agree with me?

 

[Hurkyl]

What is the one-point space?

The topological space with only a single point in it.

I have concluded that not every graph can be recovered from its geometric realization. Before I go on, does anyone else agree with me?

I agree. The realizations of

. __ . __ .

and

. __ .

would be homeomorphic.


If we restrict ourselves to graphs that don't have vertices of degree 2, however, we can always recover the graph from its realization.

 

[Oxymoron]

Exactly! So, we can always construct a geometric realization from a graph, but it is not always possible to recover a graph simply from its realization?

 

[AKG]

For (1.) I said since path length is never negative, the minimum path length is never negative. Is that enough?

What about a disconnected graph? You might have two points for which d(P,Q) is undefined.

For (2.) I said if P=Q then there is no path between them hence the path length is 0, and conversely if d(P,Q) = 0 then there is no path and hence the vertices are the same, i.e. P=Q.

It's not that there's no path between them, it's that the smallest path consists of no edges.

For (3.)

In general, 3 only holds if the graph is undirected.

If 4 were false, then the shortest distance from P to Q would be greater than the shortest distance from P to R plus the shortest dist. from R to Q. But then you could just create a path from P to Q via R which would be shorter than the supposedly shortest path from P to Q, contradiction.