Is there a method for determining if a graph (undirected) is connected?

Question

The textbook used in our class defines a connected (undirected) graph if for any two vertices $v,w\in G$ there is a path from $v$ to $w$. The examples used in the textbook show a visualization of a graph and say "observe that G is connected" or "notice that G is connected". Is there a method to determine if a graph is connected solely by looking at the set of edges and vertices (without relying on inspection of a visualization)?

Answer 1

Yes you could, but when you are human (and not a computer), I recommend you do not.

There are several ways to formally write "A graph is connected", e.g.:

1. A graph $G=(V,E)$ is connected when for all proper (i.e. $S\neq\varnothing$) subsets $S\subsetneq V$ there exist $u\in S$ and $v\in V\setminus S$ such that $(u,v)\in E$.
2. A graph $G=(V,E)$ is connected when for all distinct $u,v\in V$ there is a number $n\in\mathbb{N}$ and elements $u=v_1,v_2,\dots,v_{n-1},v_n=v$ such that $(v_k,v_{k+1})\in E$.
3. A graph $G=(V,E)$ is connected when, given some vertex $v_0\in V$, the connected component of $v_0$ is all of $G$.

You could check these by hand, e.g. to check 1. you can just write down all possible proper subsets of $V$ and then for each write down some edge connecting it with its complement. Checking 3. is more efficient, and when you are a computer this is how I would let you do it:

Let $S$ be the set of all vertices connected to $v_0$. We will construct $S$ as follows (This is a "greedy" approach):

1. We know that $v_0\in S$.
2. For all $v$ that we know are in $S$, add the vertices connected to these $v$ to the known members of $S$.
3. When we do not add new vertices, we are done. $G$ is connected when we added all vertices.

Answer 2

You could also run algorithms such as Dijkstra's, repeating it $n = |V|$ times for each node in the graph. It would give the distance from every vertex to every other, so you just check it is finite for all.

Alternatively, using the adjacency matrix $M$ of the graph, you can compute $\sum_{i=1}^{n} M^i$ and check that all the entries are strictly positive, meaning there exist a path from every pair of vertex to every other in $n$ step or less.

Answer 3

Yes. If you compute the Laplacian matrix of your graph, if the second eigenvalues of the Laplacian matrix is different from zero, your graph is connected.