Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

As the title says, let $k \geq 2$ be a positive integer and let $G$ be a $(k-1)$-edge-connected $k$-regular graph with an even number of vertices. Then, for every edge $e$ of the graph there is a perfect matching of $G$ containing $e$.

First, I was wondering if this is new and if there are approaches different from mine (and for that reason I won't mention my idea at this point)

Some background: The particular case k=3 is a theorem of Petersen; I had it as a graph theory exam problem last year; my solution led to this generalization.

share|improve this question
add comment

2 Answers 2

up vote 5 down vote accepted

If you look at the math review of the following:

MR0317999 (47 #6548) Plesník, Ján Connectivity of regular graphs and the existence of 1-factors. Mat. Časopis Sloven. Akad. Vied 22 (1972), 310–318.

You will see that this result was already known in 1972, and if you look at the actual paper (available for free on the Czech digital text collection), the author attributes it to C. Berge, proved in his graph theory book (1958) (where this is the content of theorem 6 and 7 of Chapter 18).

So, alas, this is not new.

share|improve this answer
    
Errr, I hate how everything not too convoluted has been already found in Graph Theory! Anyway, I can't access the paper to see the author's proof. I myself did it with Tutte's matching theorem/lemma. Other ideas? –  Cosmin Pohoata Oct 23 '11 at 19:40
    
The proof is in Berge's book, which used to be a standard graph theory reference, so is certainly in your university library. –  Igor Rivin Oct 23 '11 at 20:27
    
Found it, thanks. –  Cosmin Pohoata Oct 24 '11 at 1:30
add comment

Ugh I just lost my post but the short version is that on top of Igor's answer, it is easy to prove this using Edmonds' characterization of the perfect matching polytope, which implies putting weight 1/k on every edge will give you a vector in the polytope. From this fact the matching-coveredness is straightforward.

EDIT:

Edmonds proved that a vector (i.e. an edge-weighting $w(e)$) is in the perfect matching polytope (i.e. the convex hull of incidence vectors of perfect matchings) if and only if the following hold:

1) Every edge has weight in $[0,1]$.

2) Every set $S$ of vertices with odd size has $\sum_{e\in\delta(S)} w(e) \geq 1$, where $\delta(S)$ is the set of edges with exactly one endpoint in $S$.

3) Every vertex $v$ satisfies $\sum_{e\in\delta(\{v\})} w(e) = 1$.

It is an easy exercise show that these conditions are necessary, but as Edmonds proved, they are also sufficient. This implies immediately that if $G$ is a $k-1$-edge-connected graph that is $k$-regular, the vector with every edge getting weight $1/k$ is in the perfect matching polytope of $G$ (in other words, $G$ is fractionally $k$-edge-colourable). Since the weight vector is nonzero everywhere, every edge must be contained in at least one perfect matching. (Again in other words, since only perfect matchings can be used to fractionally $k$-edge-colour a $k$-regular graph, every edge must be in a perfect matching.)

share|improve this answer
    
Sorry, I was going through this again, and I'm having trouble understanding this approach. Can you please offer more details? Thanks. –  Cosmin Pohoata Feb 19 '12 at 21:46
1  
Yes, I just added the missing details. Additionally I originally said "stable set polytope" when I meant to say "perfect matching polytope". Hope this helps. –  Andrew D. King Feb 21 '12 at 22:29
add comment

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.