The game on the graph $ G$ is defined as follows. Initially, the chip is located at one of the vertices (let’s call it the starting one). The players take turns, on each move it is necessary to move the piece along any outgoing edge to the vertex, where the piece has never been. The one who cannot make a move loses. How to Prove that the former wins if and only if the starting vertex lies in all maximal matchings?

# Tag: matchings

## Perfect matchings and edge cuts in cubic graphs – part 1

Let $ G$ be a bridgeless cubic (simple) graph, and let $ M$ be a perfect matching in $ G$ . $ G-M$ will necessarily be a set of circuits. For example, if we delete a perfect matching from $ K_{3,3}$ we end up with one circuit. If we delete a perfect matching from the Petersen graph we end up with two circuits. And in general, one could end up with many. The following question comes to mind.

QuestionLet $ G$ be a cubic bridgeless (simple) graph which is cyclically edge-5-connected, and let $ M$ be a perfect matching in $ G$ . Is there a subset $ K$ of edges in $ M$ such that $ G-K$ has exactly two components, such that either none of the two components are circuits, or both are circuits?

For example, any perfect matching in the Petersen graph is an example of such an edge cut.

A graph $ G$ is *cyclically edge-5-connected* if no set of fewer than 5 edges is cycle separating. A set $ K$ of edges is *cycle separating* if $ G-K$ is disconnected and at least two of its components contain circuits.

## How can I find matchings in a Bipartite graph beginning with specific vertices?

Context: I’m modelling kidney exchanges through directed acyclic graphs. I convert these to Bipartite graphs (by splitting each node into a donor and receiver, and the edge from the original graph exist between corresponding donors and receivers). I want a way to find maximum number of edges through disjoint chains and I’ve been trying to do so through maximum wtd matching.

I know I can use ford-fulkerson to find a maximum wtd perfect matching, however, the main problem I’m facing is that the matchings can only exist for chains beginning with *specific* vertices. For example, if this is my directed acyclic graph:

Turning this into a Bipartite graph and using the maximum wtd matching way, I get the chain 0->1->3->5->6 but I also get 2->4. However, I can only have chains beginning with 0 so 2->4 should not come up.

I wanted to know if there were any ways to work around this problem? Someone suggested making this a minimum cost perfect matching problem but I’m confused how.

I realise this is a weird question but any help would be appreciated!

## Maximum number of perfect matchings in a graph of genus $g$

What is the maximum number of perfect matchings a genus $ g$ balanced $ k$ -partite graph (number of vertices for each color in all possible $ k$ -colorings is within a difference of $ 1$ ) can have? I am particularly interested in $ k=2$ .

## Expected size of matchings in a cubic graph

Let $ G$ be a random cubic graph on $ n$ vertices. Let $ M$ be the set of (not necessarily maximum) matchings of $ G$ . What is the expected size (i.e. number of edges) of an element of $ M$ ?

In other words, what is the typical size of a matching in a typical cubic graph?

The Bethe lattice approximation gives the number $ \frac{3}{10}n$ , which coincides with experimental results. I’m wondering whether it is the true number.