In graph theory, a graph is connected when all of its nodes are directly or indirectly linked together with edges. That is, if there is a path between every two different nodes.

A directed graph is strongly connected if there is a directed path from every node to every other node.

A maximal connected subgraph of a graph is called a component of the graph.

In topology, an important axiom of topological spaces.

Definition A topological space X is said to be disconnected if there are nonempty subsets A,B of X such that AnB={}, AuB=X, and A and B are both open in X.

Since A and B are complements in X, it follows that they must both be closed. So we could replace 'open' with 'closed' in the definition above. I will refer to A and B as a 'disconnection' of X (which isn't standard terminology). It's reasonably clear that the following is equivalent:

Lemma X is disconnected iff it has a proper, nonempty subset that is both open and closed.

Definition A topological space X is connected if it is not disconnected. A subset Y of a topological space is connected if Y is connected in the subspace topology inherited from X.

This definition sounds a bit odd at first, but it does give the desired effect - that is, the spaces you would expected to be connected are, and vice versa. Having said that, for spaces which aren't well separated (ie. they don't satisfy many separation axioms), deciding whether a space is connected can be far from an intuitive matter.

A more intuitive (and stronger) concept is that of path connectedness.

The following are the basic results about connectedness, leading to a proof of the connectedness of Rn; they're all pretty intuitive, and all have pretty basic proofs. Since the definition of connectedness is in negative terms, stating that a space is not disconnected, all the main proofs are by contradition.

Theorem X=[0,1] is connected.

Proof Suppose not. Then there are subsets A, B with AuB=X, AnB={}, A,B both open in X. Then 1 is in A or 1 is in B; suppose it's in A. Then, B is nonempty, and bounded above by 1, so it has a supremum b.

Now, if b is in B, then b>1 since 1 is in A, and everything above b is in A. But B is open, so B must contain a small open interval centred on b, which must contain points above b, which is a contradiction.

And if b is in A, then A contains a small open interval centred on B. But every open interval centred on b contains points of B, since b is the supremum of B, and this is also a contradiction.

So [0,1] is connected.

Proposition The continuous image of a connected space is connected.

Proof Let X,Y be topological spaces, X connected, f:X->Y continuous and onto. Suppose Y is disconnected; then there is a disconnection A,B of Y. Then f-1(A), f-1(B) forms a disconnection of X, contradicting connectedness of X.

Proposition If X is a topological space, Z is a connected subset of X, and Y is a subset of X containing Z and contained in the closure of Z, then Y is connected. In particular, if Z is connected then the closure of Z is connected.

Proof Suppose A,B is a disconnection of Y. Then AnZ, BnZ is a disconnection of X.

Proposition Suppose (Xi)i in I is a collection of connected spaces such Intersection(Xi) is nonempty. Then Y=Union(Xi) is connected.

Proof Suppose A,B is a disconnection of Y, and suppose x is in Intersection(Xi). Then either x is in A or x is in B; suppose x is in A. Also, B is nonempty, so there is some i such that Xi contains a point of B. Then XinA and XinB are nonempty, so they form a disconnection of Xi.

Corollory R is connected.

Proof Define fn:[0,1]->R by f(x)=2n(x - 1/2), so that fn([0,1]) = [-n,n]. Then [-n,n] is the continuous image of the connected space [0,1], and so is connected. And R is union of the sets [-n,n] for n in N which have nonempty intersection, so R is connected.

Proposition If X,Y are connected spaces then XxY is connected.

Proof Suppose A,B is a disconnection of XxY. Then there are points (xA, yA) in A, (xB, yB) in B. Let C be the subspace {(xA,y) in XxY : y in Y} and D be the space {(x, yB) in X,Y : x in X}. Then C is clearly homeomorphic to Y, D is clearly homeomorphic to X, so both are connected. Moreover, the element (xA, yB) is in both spaces, so their union Z=CuD is connected. But ZnA, ZnB form a disconnection of Z, which is a contradition.

Corollory Rn is connected.

I find it interesting to note the difference between the graph theory and the topological definitions of connectedness when we apply both to society.

The graph theory definition means that people are connected with things, such as phonelines.

The definition given by topology is far more thought provoking. Society is divided into sets. To make things interesting, lets consider one partition based on culture. Is society connected? For this to be true, society cannot be decomposed into a set of disjoint subsets. This is to say that in each culture, there must be a member who is also a member of some other culture. In other words, for society to be topologically connected, every culture must contain people who are "poly-cultural". This was certainly untrue back in the days when society was disconnected in the graph theory sense, but I would like to postulate that a result of connectedness in the first sense will be connectedness in the second sense, eventually giving rise to a global village.