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)$.

  • $\begingroup$ I know every regular graph of odd order is of class two, so H is of order two. I can't proof that G is of class two? $\endgroup$ May 26, 2017 at 16:35
  • $\begingroup$ @ yaodao vang: Reading only the first two lines of this question, one wonders if $\frac12(\Delta(H)-1)$ is meant to suggest that $\Delta(H)$ is 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$ May 26, 2017 at 19:34
  • $\begingroup$ Also, please use the standard $\chi'(G)$ instead of $x_1(G)$ for the chromatic index. $\endgroup$ May 26, 2017 at 19:36

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.