Undirected graph 1 degree checking Given an undirected graph, which consists of n vertexes and m edges. Provided we can delete edges from the graph. Now we want to check is it possible to delete edges in the graph so that the degree of each vertex in the graph will be equal 1?

There can be multiple edges in the graph, but can not be any self loops.

EXAMPLE : Consider n=4 and m=6 and let edges be (1,2),(1,3),(1,4),(2,3),(2,4),(3,4).

Then answer would be "TRUE".As it is possible to delete edges to get every vertex with degree 1.
This basically boils down to figuring out whether or not the graph contains a perfect matching; a matching that uses every vertex.

If such a matching exists, then we simply remove every edge that isn't in the matching. Similarly, if we are able to remove edges so that every vertex has degree 1, we're necessarily left with a perfect matching.

In that Wikipedia article I linked to, there's a link to Edmond's blossom algorithm, which is used to find the maximum matching (i.e. matching with the largest number of edges) of a graph. To find whether a graph has a perfect matching, you could run that algorithm and see if the maximum matching is a perfect matching.
Just check whether the graph is 1-Regular or not. You can find more on Regular Graphs on Wikipedia Regular Graph