Let $H$ be a nonempty regular graph of odd order and let $G$ be a graph obtained from $H$ by deleting $\frac{1}{2}(\Delta( H)-1 )$ or fewer edges. How to show that $G$ is of class two? a graph is of class two when$x_1(G)=\Delta(G)+1$ and belong class one when$x_1(G)=\Delta(G)$ . that $x_1(G)$ is a minimum colors need to color the edge of graph ,such that adjacent edge have a different color. Or the smallest number of colors needed in a (proper ,meaning no two adjacent edges are assigned the same color) edge coloring of $G$ is a chromatic index , or edge chromatic number or $x_1(G)$.

## 1 Answer

If order means a number $2k+1$ of vertices, we simply note that each color has at most $k$ edges, so $d=\Delta(H)$ colors have at most $dk$ edges, thus at least $d/2=|E|-dk$ edges must be removed from $H$ for getting a graph of class 1.

odd. It does not follow from what you wrote. (E.g. the complete graph $H$ on three vertices is non-empty, regular, of odd order, but has $\Delta(H)=2$, and hence $\frac12(\Delta(H)-1)$ non-integral.) Please, clarify whether $\Delta(H)$ is assumed to be odd. $\endgroup$