Graph Edges Deletion

Question

We are given a undirected graph without loops.We have to check if it is possible to delete edges such that the degree of each vertex is one.

What should I try to this question? Should I use adjacency matrix or list.

Please suggest me the efficient way.

Answer 1

If the graph needs to be fully connected, it's possible if and only if there are exactly two vertices and they have an edge between them.

---

If it does not need to be fully connected you must search for a similar constellation. That is, you need to see if it is possible to partition the graph into pairs of vertices with one edge in each pair. That is what we are after. What do we know?

The graph has no loops. This means it must be a tree! (Not necessarily binary, though). Maybe we can solve this eagerly by starting at the bottom of the tree? We don't know what the bottom is; how do we solve that? We can decide this ourselves, so I decide to pick all the leaves as "bottom".

I now propose the following algorithm (whose efficiency you may evaluate yourself, it isn't necessarily the best algorithm):

1. For each leaf L:
   1. Let P be the parent of L, and Q the parent of P (Q may be NULL).
   2. Is the degree of P <= 2? That is, does it have only one edge connecting it to L, and possibly one connecting it to Q?
      1. If no: Pick another leaf L and go to 1.1.
      2. If yes: L and P can form a pair by removing the edge between P and Q. So remove L and P from your memory (in some way; let's come back to data structures later).
2. Do we have any vertices left in the graph?
   1. No: The answer is "Yes, we can partition the graph by removing edges".
   2. Only one: The answer is "No, we cannot partition the graph".
   3. More:
   4. Did we remove any nodes?
      1. If yes: Go back to 1 and check all the current leaves.
      2. If no: The answer is "No, we cannot partition the graph".

So what data structure do you use for this? I think it's easiest to use a priority queue, perhaps based on a min-heap, with degree as priority. You can use a linked list as a temporary storage for leaves you have already visited but not removed yet. Don't forget to decrease the priority of Q in step 1.2.2.

But you can do even better! Add all leaves (vertices with degree 1) to a linked list. Loop through that list in step 1. In step 1.2.2, check the degree of Q after removing L and P. If the degree is 1, add it to the list of leaves!

I believe you can implement the entire algorithm recursively as well, but I let you think about that.