# Prove Graph G is in Vizing Class 2 if $\alpha$'(G) < |e(G)|/$\Delta$(G)

G is a simple graph with e edges, maximum vertex degree $\Delta$ and edge independence number $\alpha$' which satisfies $\alpha$' < e/$\Delta$.

What does this inequality mean? How is it helpful in proving that G is Vizing Class 2?

I'm struggling to understand what property of G this inequality implies. This inequality obviously works for graphs known to be in Vizing Class 2, like odd cycle graphs, but I'm not sure if I should be reasoning backwards like that.

I discovered the answer was simpler than I thought.

$\alpha$' < e/$\Delta$ --> $\Delta$ < e/$\alpha$'

$\chi$' >= e/$\alpha$'

$\chi$' > $\Delta$

Notice that the edge independence number $\alpha^\prime$ is the size of a maximum matching. Also, in any proper edge coloring, the set of all edges of a given color (a color class) forms a matching.

So given a proper edge-coloring with $\chi^\prime(G)$ colors, each color class $C_i$ can have at most $\alpha^\prime$ edges. So we have \begin{eqnarray*} |E(G)| &=& |C_1|+|C_2|+\cdots + |C_{\chi^\prime(G)}| \\ &\leq& \alpha^\prime+\alpha^\prime+\cdots + \alpha^\prime \\ &= &\alpha^\prime\chi^\prime(G).\end{eqnarray*}

But if you're given that $|E(G)|>\alpha^\prime\Delta(G)$, then combining the two inequalities gives $\Delta(G)< \chi^\prime(G)$. So by Vizing's Theorem, $\chi^\prime(G)$ can only equal $\Delta(G)+1$.