3
$\begingroup$

Let $G = (V, E)$ be a simple, undirected graph. We consider the following two definitions of graph connectedness:

(1) $G$ is connected if for $x,y \in V$ there is a finite path connecting $x$ and $y$.

(2) If $A \subseteq V$ such that $A \neq \emptyset$ and $A \neq V$ there is $e\in E$ such that $e \cap A \neq \emptyset$ and $e \cap (V\setminus A) \neq \emptyset$.

It is not hard to see that for finite graphs, (1) and (2) are equivalent, and that (1) implies (2) in the general case.

Is there an infinite graph that is connected with in the sense of definition (2), but not in the sense of definition (1)?

Improve this question
$\endgroup$
5
  • 8
    $\begingroup$ Doesn't (2) => (1) follow by taking some connected component for $A$? $\endgroup$
    – Martin Brandenburg
    Commented May 14, 2012 at 7:36
  • 5
    $\begingroup$ If you view a graph as a CW complex, then (1) is "path-connected" and (2) is "connected", and they are equivalent because CW complexes are locally path-connected. $\endgroup$
    – Will Sawin
    Commented May 14, 2012 at 8:02
  • 5
    $\begingroup$ I think this question is better suited for math.stackexchange $\endgroup$
    – Gjergji Zaimi
    Commented May 14, 2012 at 8:11
  • 1
    $\begingroup$ To Martin's comment add: where a connected component is defined to be the set of vertices that can be reached via a path from some fixed vertex. (We can't assume "connected component" is well-defined before knowing whether "connected" is well-defined.) $\endgroup$
    – Brendan McKay
    Commented May 14, 2012 at 9:46
  • $\begingroup$ @Brendan: Sure, but this is also the usual definition. $\endgroup$
    – Martin Brandenburg
    Commented May 14, 2012 at 10:38

1 Answer 1

Reset to default
1
$\begingroup$

To be more explicit, fix a vertex a and let A0 be the singleton set having a as a member. Using the mechanism of (2) and some version of the axiom of choice, define An+1 by adding the one vertex that is guaranteed to be adjacent to but not in the vertex set An. Take the union of these sets and call it A. Now either A is all of V or else something went horribly, horribly wrong. The remaining details of (1) are left to the (horrified) reader.

Gerhard "And I Do Mean Horribly" Paseman, 2012.05.14

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Of course, one horrible possibiliity is that V is not countable, in which case one needs to add more than one vertex at a time. There are other considerations as well, but I will let others expound on those. Gerhard "Not A Professional Set Theorist" Paseman, 2012.05.14 $\endgroup$
    – Gerhard Paseman
    Commented May 14, 2012 at 15:47
  • 1
    $\begingroup$ Don't you want to say, fix a vertex $x$ and let $A$ be the set of all vertices $y$ such that there is a finite path connecting $X$ and $Y$? That should answer every consideration. $\endgroup$
    – Will Sawin
    Commented May 14, 2012 at 16:06
  • 1
    $\begingroup$ No need for the axiom of choice. Given (2), just let A be the set of vertices connected to a by a path, and B its complement. Then there can be no edges joining A and B, and so A=V, and so (1) is true. $\endgroup$
    – Jeremy Rickard
    Commented May 14, 2012 at 16:08
  • 1
    $\begingroup$ Being a student of foundations, I like to have people consider the basic construction first, and realize that more care needs to be taken. (I could then plu Greg Moore's book on the history of AC, and beat the foundations drum some more.) So to directly answer Will, not really. Addressing the actual problem though, Will's and Jeremy's suggestions do show more care. Gerhard "Ask Me About System Design" Paseman, 2012.05.14 $\endgroup$
    – Gerhard Paseman
    Commented May 14, 2012 at 16:16

Not the answer you're looking for? Browse other questions tagged .