# maximal matching in graph theory

if we have a graph $G = (V,E)$ and the four values $\beta_1(G)$, $\alpha_1(G)$, $\beta(G)$, $\alpha(G)$, where

$\beta_1(G)$: Edge independence number. The maximal number of independent edges in the graph. $\alpha_1(G)$: Vertex independence number. The maximal number of independent vertices in the graph. $\beta(G)$: Edge covering number. The minimal number of edges that cover all the vertices in the graph $\alpha(G)$: Vertex covering number. The minimal number of vertices that cover all the edges in the graph.

If $\alpha(G) \le \beta_1(G)$ is is necessarily true that we have maximal matching?

I tried with some graphs and I found it true! For example

• Hi Lama, I fixed the formatting of your question. This is a short overview how to use MathJax here on MSE. Jul 5 '15 at 12:49

• Let $M$ be the matching, and $C$ be the cover.
• Observe that no two edges $e_1,e_2 \in M$ share a vertex, hence $\alpha(G) \geq \beta_1(G)$. In particular each edge $e \in M$ has exactly one of its vertices inside $C$.
• Suppose there is an augmenting path $P$, which vertices cover the unmatched edges $e \in P \setminus M$ on that path?
• How many covering vertices of $C$ do you need to cover all the vertices of $P$ and how many you can actually use?
I hope this helps $\ddot\smile$