5
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Cosmin Pohoata
    Commented Oct 23, 2011 at 19:40
  • $\begingroup$ The proof is in Berge's book, which used to be a standard graph theory reference, so is certainly in your university library. $\endgroup$
    – Igor Rivin
    Commented Oct 23, 2011 at 20:27
3
$\begingroup$

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.)

Improve this answer
$\endgroup$
2
  • $\begingroup$ Sorry, I was going through this again, and I'm having trouble understanding this approach. Can you please offer more details? Thanks. $\endgroup$
    – Cosmin Pohoata
    Commented Feb 19, 2012 at 21:46
  • 1
    $\begingroup$ 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. $\endgroup$
    – Andrew D. King
    Commented Feb 21, 2012 at 22:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .