# Given a graph $G$, how to find all disjoint edges?

I have an undirected graph $G$, with edges $E$ and vertex $V$, how to group the edges into different sets, in which

1. One edge can only belong in one set
2. Every edge must be covered in one of the sets
3. If I can "walk" from one edge to another, these two edges must be contained in a single set.

Take this for an example, I have the following edges $(A,B), (C,B), (D,B),(B,G), (E,F)$, then there are two sets, namely, $(A,B), (C,B), (D,B),(B,G)$ and $(E,F)$.

Edit: My hunch tells me that there is a standard algorithm (with a name) for this, what is it?

• I haven't studied graph theory but 1 and 2 don't make sense. It seems like they're two ways of saying the same thing, "each edge can only belong in one set", i.e. a partition on E. I just point this out because somebody that can help you might be confused too. If it's standard terminology please just excuse me. Condition 3 just defines an equivalence relation assuming that you allow a walk from an edge to itself of zero steps. Apr 6, 2011 at 10:33
• @knucklebumpler, I've edited the question. sorry for the poor wording. Apr 6, 2011 at 10:35
• @Zach, from what I know, connected component works for directed graph, not undirected graph, don't you think so? Apr 6, 2011 at 11:22
• (I posted my comment as an answer now.) Connected components exist in both directed and undirected graphs. Directed graphs, however, distinguish between "weakly" connected components and "strongly" connected components. Apr 6, 2011 at 11:25