Let $G=(V,E)$ be an undirected graph. Show:
$M\subseteq E$ is a matching if and only if every vertex of the graph $(V,M)$ has degree at most $1$.
I think the first direction follows immediately from the definition of a matching but what about the other implication?
2026-03-28 01:35:24.1774661724
$M$ is a matching iff every vertex has degree at most 1
87 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
Suppose $M \subset E$ is a matching. Then, vertices of the graph $(V, M)$ have degree at most $1$. If there is a vertex $v\in V$ with $\deg_M (v) \ge 2$, then there are at least two distinct edges $e_1,e_2 \in M$ with a common vertex $v$. This is not possible since $M$ is a matching (see the definition.)
For the other direction, suppose every $v\in V$ has $\deg_M (v) \le 1$. Then, no two edges in $M$ share common vertices (for if they did, that common vertex would have degree at least two), so $M$ is a matching.