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.
2026-03-26 21:09:22.1774559362
Let $G$ be a 5-regular graph with $|V(G)| = 10$. Prove that $G$ has a perfect matching.
109 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
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.