Let $G$ be a 5-regular graph with $|V(G)| = 10$. Prove that $G$ has a perfect matching.

109 Views Asked by At

I’ve made several attempts at this but can’t quite get there. We can use the fact that $\nu ~(G) \leq \tau ~(G)$ to bound the matching number of $G$. $|E(G)| = 25$, so if $G$ is 5-regular we require a vertex cover of $|X| = 5$, so we can then say that $\nu ~(G) \leq 5$. We could potentially also use the fact that for bipartite graphs, $\nu ~(G) = \tau ~(G)$, which proves that if $G$ is bipartite then it has a perfect matching, but then I’m not really sure how to go about addressing the case that $G$ is not bipartite which makes me think this is not the best approach.
Edit: I think it actually makes more sense to approach this using Tutte's theorem, which is that a graph has a perfect matching if and only if for all $X \in V(G)$, the number of connected components with an odd number of vertices in $G - X$ is less than or equal to $|X|$.
For $|X| \in \{5,6,7,8,9\}$, even if every remaining vertex in $G - X$ is an odd component, we would still satisfy that the number of odd components in $G - X$ is $\leq |X|$, so we need only consider X of the form $|X| \in {1,2,3,4}$ G is 5-regular, therefore it is impossible to have any component of size 1 by deleting less than 5 vertices. $|X| = 4$: it is impossible for the remaining 6 vertices to form 4 or more components of odd size without any components composed of a single vertex, which we established is impossible for $|X| < 5$. Analogous arguments hold for $|X| = 3$ and $|X| = 2$ For the case that $|X| = 1$ we are guaranteed to be left with 1 odd sized component.

1

There are 1 best solutions below

0
On BEST ANSWER

And in my opinion it is easier to use Dirac's theorem that a simple graph with $n$ vertices ($n\geq3$) is Hamiltonian if every vertex has degree $n/2$ or greater.

Having a Hamiltonian cycle it is easy to construct a perfect matching.

Try it.