Graph theory (Perfect matchings)

Question

In an undirected graph with 2024 vertices (not necessarily bipartite) between any three vertices have at least two edges. Prove that the graph contains a perfect matching (from 1012 edges).

To be honest, I have already tried everything I could, in the lectures I was told mainly about theorems that can be applied to bipartite graphs (Hall’s Theorem, König’s Theorem), but the problem says that the graph is not necessarily bipartite. Maybe we need to somehow rely on the fact that this graph probably could be a complete graph?

Answer 1

HINT:

1. Let $M$ be a matching that leaves at least $2$ vertices $u$ and $v$ unmatched. [The number of vertices left unmatched in this graph $H$ must always be even--why is that].

2. Next let $u'v'$ be any edge in this matching $M$.

3. Then the condition that there are $2$ edges between any $3$ vertices gives us the following: either $uv$ form an edge in $H$ [and so $M +\{uv\}$ is also a matching but w one additional edge] or both $uu'$ and $vv'$ form an edge in $H$ [and so $(M -\{u'v'\})+\{uu',vv'\}$ is also a matching in $H$ w one additional edge]...

Can you finish from here.

Answer 2

Given that graph is not necessarily bipartite but it still satisfies the condition that between any three vertices there are at least two edges, we can construct a bipartite graph from the original graph annd then proceed applying Hall's Marriage Theorem:

Hall's Marriage Theorem states that a bipartite graph has a perfect matching if, for every subset S of vertices on one side (let's say Set A), the neighborhood of S (vertices connected to vertices in S) has a size greater than or equal to the size of S.

The condition "Between any three vertices, there are at least two edges" ensures that the neighborhood of any subset S in Set A is large enough to satisfy Hall's condition.

In other words, because there are at least two edges between any three vertices, when we connect vertices from Set A to vertices in Set B, the neighborhood of any subset in Set A will be sufficiently large.