From Wikipedia

Graphs have path connected subsets, namely those subsets for which every pair of points has a path of edges joining them. But it is not always possible to find a topology on the set of points which induces the same connected sets. The 5-cycle graph (and any n-cycle with n>3 odd) is one such example.

As a consequence, a notion of connectedness can be formulated independently of the topology on a space. To wit, there is a category of connective spaces consisting of sets with collections of connected subsets satisfying connectivity axioms; their morphisms are those functions which map connected sets to connected sets (Muscat & Buhagiar 2006). Topological spaces and graphs are special cases of connective spaces; indeed, the finite connective spaces are precisely the finite graphs.

However, every graph can be canonically made into a topological space, by treating vertices as points and edges as copies of the unit interval (see topological graph theory#Graphs as topological spaces). Then one can show that the graph is connected (in the graph theoretical sense) if and only if it is connected as a topological space.

I was wondering if the two bold sentences contradict each other?

Thanks and regards!

  • $\begingroup$ Actually, I don't understand that quote-- I can't see (at all!) why it is important to consider "$n>3$ odd". Why is there a topology on the 4-cycle with the same connected components (just one component, right?) but not on the 5-cycle? Can anyone clarify? $\endgroup$ – Matthew Daws Jan 29 '12 at 20:27
  • $\begingroup$ @MatthewDaws: azarel has answered my original questions. I think a better way is to make our further questions into a new post. Could you do that, or I may sometime? $\endgroup$ – Tim Jan 29 '12 at 20:55
  • $\begingroup$ Okay, new question here: math.stackexchange.com/questions/103702/… $\endgroup$ – Matthew Daws Jan 29 '12 at 21:12
  • $\begingroup$ @MatthewDaws: Thanks for making it real and linking it here! Just gave it an upvote for promoting it. $\endgroup$ – Tim Jan 29 '12 at 21:14

They don't contradict each other as they refer to completely different things.

To make it more precise: If $G$ denotes the $5$-cycle graph then the first statement implies that there is no topology on the vertices of $G$ which has the same connected subspaces.

On the other hand, In the second statement we are identifying the graph $G$ with a pentagon which is not the same as a $5$-element space.

  • $\begingroup$ Thanks! (1) Could you explain why "there is no topology on the vertices of G which has the same connected subspaces"? (2) How are things different when identifying the graph G with a pentagon? Is the pentagon just a subset consisting of boundary points, or does a pentagon also include the area the boundary encloses? $\endgroup$ – Tim Jan 29 '12 at 18:39
  • $\begingroup$ @Tim: Yes-- in the first case, we consider just the 5 points. I guess the topology is required to have some properties (as the indiscrete topology would be connected)-- certainly being Hausdorff is enough to force the discrete topology. In the 2nd space, we consider the "pentagon" to include its sides-- that's what the original quote "edges as copies of the unit interval" means. $\endgroup$ – Matthew Daws Jan 29 '12 at 19:58
  • $\begingroup$ @MatthewDaws: Thanks! So do you mean the topology being Hausdorff is a necessary condition for making the two types of connectedness equivalent? Then how shall we explain there is no topology on the set of vertices that can make the two connectedness concepts equivalent? $\endgroup$ – Tim Jan 29 '12 at 20:06
  • $\begingroup$ @Tim: No, I mean that if you insist that a topology on the set of vertices of a finite graph is Hausdorff, then it must be the discrete topology. You could define a different topology by saying that the collection of open sets was exactly the path connected components of the graph, and then you'd have a topology who connected components agreed with the path connected components. But this topology wouldn't be Hausdorff-- it wouldn't even "topologically distinguish" points-- and so it would be a pretty useless topology! $\endgroup$ – Matthew Daws Jan 29 '12 at 20:15
  • $\begingroup$ @Tim: See my comment on your original post-- I'm actually quite confused about that the Wikipedia quote means! $\endgroup$ – Matthew Daws Jan 29 '12 at 20:28

Actually the 5-cycle (as points) does not admit ANY topology (Hausdorff or not) which gives the same connected sets (ie the edges and paths). This follows by considering that each non-edge induces two open sets. One can prove that each open set will have to be either a set {x} or {y,x,z} where y-x-z are connected, with each type alternating. This implies in turn that any odd cycle cannot have a compatible topology (except 1,3).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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