Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have this problem from graph theory:

Given a graph $G = (V,E)$ (maybe with multiple edges) find if it's possible to delete some edges such that the new graph is 1-regular (ie. all of its vertices have degree 1).

So far I have only discovered that if number of vertices is odd then it's impossible, this is an easy consequence of the degree formula $\sum_{v \in V} \deg(v) = 2|E|$. Also I can consider there are no multiple edges or loops since I can delete them without affecting the result.

Now if I consider the adjacency matrix of the graph then the resulting adjacency matrix for the new graph must have determinant 1 or -1 because I can get it by permuting the rows/columns of the identity matrix.

I'm guessing two things one bolder than the other. If the number of vertices is even and every vertex has degree at least one it is always possible to get a 1-regular graph and second, if the adjacency matrix of the original graph has determinant 1 or -1 it is possible to delete some edges to get a 1-regular graph. (Maybe deleting edges can be translated to using a pivot to delete some entry in the matrix?)

May someone give me some hints/help or a counterexample to my guessing?

share|improve this question
    
I wonder why there's been so many questions on MSE over the last few weeks that use exactly the same convoluted expression to describe "has a perfect matching"... –  Erick Wong Jan 11 at 2:08

2 Answers 2

up vote 3 down vote accepted

You are asking whether a graph has a perfect matching, which is a well-studied problem in graph theory and computer science. In particular, the Tutte theorem gives a (not so easy to check) characterization.

share|improve this answer

For your first guess, consider the following graph: enter image description here

I will continue to think about the second guess...

share|improve this answer
    
thanks, the first one was the bolder one :) –  Vicfred Jan 11 at 1:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.