Consider the following graph:
https://i.imgur.com/r9d38v2.png
The vertex 1,2,3,4 belong to the first set and the vertex 5,6,7,8 belong to the second set. We want to check if its possible for each vertex from both sets to be connected to only one vertex from the other set. In other words if there are 8 nodes then there will be 4 different edges each one connecting different pairs of nodes. Is this a well known problem and how to solve it?
Could we not use some technique like "peeling the onion" and resolve all vertices of indegree 1, then 2, then 3...? If we resolve all nodes then the condition is possible, if there are leftovers, then it is impossible. I would attempt the problem using an array to keep track of the degree of each vertice and process them topologically.
Please phrase your question properly. What do you mean by "possible"? What is the point of the existing edges in the graph? Also, what operations can we do? Can we add edges or remove edges? Also what is the starting graph that we are supposed to work on? Also, what do you mean by connected? Is it that there is some path from one edge to the other or is it that they are directly connected by a single edge? Please make your question a bit clearer before you post it.
Maybe you can just post the link of where you got the question from so it will be clearer? thanks.
Yes, this problem is well known and it's called bipartite matching.
I won't elaborate further, have fun researching about it! There are tons of resources about it in codeforces, cp algorithms, topcoder and about anywhere.