A graph is called matching-covered if every edge is containd in a perfect matching. (Such graphs are also sometimes called "elementary", e.g. in Chapter 4 of "Matching Theory" by L …

Hello Is it possible to decide whether a given or calculated lower bound is the optimal solution for a problem, like a Arc Routing Problem? If yes, when is a lower bound the optim …

Suppose a bipartite graph $G=(V_1 \cup V_2, E)$ is given, and one is interested in matching vertices $V_1$ to vertices $V_2$. Assume Hall's condition does not hold, so a perfect ma …

Suppose a bipartite graph $G=(V_1 \cup V_2,E)$ is given, and a weight $w_e \geq 0$ is associated with each edge $e \in E$. The interest is to match vertices $V_1$ to vertices $V_2$ …

Sorry, this is going to be technical and dirty. I am not looking for a proof of the Edmonds-Gallai structure theorem (I understand two of them, even if they are rather similar); I …

Edit Tony's answer is quite nice, but I meant something else. Sorry for editing again, I meant edges. I am looking for a graph with 3 distinguished edges $xx'$,$yy'$,$zz'$ where $ …

I am looking for a simple degree conditon that ensures the existence of a k-factor in a graph. The k is supposed to be relatively high and I don't mind the condition being a bit st …

This might be the most stupid question I am ever posting here: I am asking for a proof or a counterexample to a problem I proposed on MathLinks long ago. Let $G$ be a bipartite gr …

Disclaimer: This is a question I have not done any real research about. I asked it myself some 5 years ago, and back then I had no idea where to start. Now I have some texts on sta …

I am interested in the following question: For which sets ${m_1,\ldots m_k}$ of positive integers do there exist bipartite graphs having exactly $m_i$ matchings of size $i$ for ea …

I have the following problem: Let $ \mathcal{G} = (G_{i})_{i} $ be a collection of graphs. I would like to find a "system of representative edges" $ f : \mathcal{G} \rightarrow \b …