# to find disconnected graphs

We know that if in a graph $G$, $e$ < $(n -1)$, then the graph is disconnected, where $e$ and $n$ are number of edges and number of vertices resp. Is there any other criteria to find out the disconnected graphs. Thanks for your help.

• There's a nice formula that is often useful: $V-E=b_0-b_1$ where $V,E$ are the number of vertices and edges, $b_0$ is the number of connected components and $b_1$ is the "number of loops," which can be defined as the number of edges in the complement of a spanning forest. – Cheerful Parsnip May 6 '13 at 12:58
• Sir, Is there any specific name of this formula? It means if we are taking simple graphs, then $b_1$ is zero. And if $V$ - $E$ = $b_0$ is greater than 1, we will get disconnected graphs. Am i right sir? – monalisa May 6 '13 at 13:25
• One quick and dirty algorithm, for a graph with n vertices, sum the first n powers of the adjacency matrix. If there are no zeros in the sum, it's connected. This is slower that the standard algorithms, but it's a one-liner program. – Ed Pegg May 6 '13 at 15:08
• @monalisa: this is called the Euler characteristic. The loops I am referring to are not the same as what you are thinking, though. For me a loop is a "hole" in the graph, and as I mentioned in my comment, this can be rigorously defined as the number of edges in the complement of a spanning forest. – Cheerful Parsnip May 6 '13 at 18:13