# Given a list of edges, how many connected components can be found?

Given a list of edges such that the undirected graph generated cannot have multiple edges but can have loops. How many connected components can be found?

This is best demonstrated with an example. Given this list of edges:

A -- A
A -- B
B -- C
B -- D
B -- F
G -- H
H -- I
I -- G


There are two connected components that can be found:

Is there a way to determine how many connected components can be found without actually constructing the graph?

• What kinds of graphs are you thinking of? Simple graphs? Also, are you only allowed to consider graphs with these eight exact vertices? Commented Oct 19, 2019 at 16:40
• @TeddantheTerran I'm not familiar with graph theory terminology yet, so forgive me if I don't answer well. I'm considering any number of vertices. Just given list of edges where the number of edges is any positive number. These are directed graphs, so I don't think they are considered simple, no. I have an image of my example graph in my question if that helps. Commented Oct 19, 2019 at 16:47
• No problem! But if you allow any set of vertices that includes A, B, C, D, F, G, I, and H, then there are infinitely many graphs that satisfy your conditions, so there must be some kind of restriction. Commented Oct 19, 2019 at 16:54
• I'm not sure I understand. Could I just add vertex X to your picture without any edges? Would that count? Could I add some extra edges? Or do you want a digraph with exactly these vertices and exactly these edges? Commented Oct 19, 2019 at 16:56
• @saulspatz Yes, if you were to add a vertex X without any connections, or even something like $X \to Y$, then there would be 3 graphs in that case. Maybe I'm misinterpreting what the term graph means. Really I'm just interested in how many different sets of connected vertices are there. Commented Oct 19, 2019 at 17:09

## 1 Answer

I ended up using a depth first search approach to solving this:

a) Pick a random node and mark as visited
b) Find all nodes adjacent and repeat algorithm on each
c) If no adjacent nodes are found, exit

d) Increment component counter by 1
e) Repeat algorithm if not all nodes in the list have been visited


This isn't a mathematical solution as I had hoped for, but it works.