# All even order graphs with $\Delta\ge\frac{n}{2}$ is Class 1

Are all even order graphs with maximum degree $$\ge\frac{|V(G)|}{2}$$ Class 1(edge-colorable(chromatic index) with $$\delta(G)$$ colors)? Here, $$|V(G)|$$ detnotes the number of vertices in the graph.

I think yes, because, by Erdos-Posa theorem on the number of maximal disjoint circuits in a graph, we have that any graph has a matching of size at least $$min(\delta(G), \frac{|V(G)|}{2})$$. Now, consider a regular graph of degree $$\delta(G)$$. Then, by the Erdós-Pósa theorem, it will have a perfect matching(as $$\delta(G)\ge\frac{|V(G)|}{2})$$, in fact, $$\delta$$ perfect matchings(I think), because each independence-induced subgraph(graph formed by deleting a set of independent vertices from the graph) would also have a 1-factor and thus, the whole graph should be 1-factorizable, that is must be Class 1. Thus, any graph with maximum degree at least $$\delta(G)$$ should be Class 1. Any hints. Thanks beforehand.

• Does it serves as a counterexample? – LeechLattice May 14 '19 at 2:13
• @Bullet51 thanks, yes it should serve as a counterexample. But, are there vertex transitive counterexamples? – vidyarthi May 14 '19 at 5:28
• Possibly not. – LeechLattice May 14 '19 at 6:12
• I thought Class1 meant edge colorable with $\Delta(G)$ colors? Why would any non-regular graph be edge colorable with $\delta(G)$ colors? – bof May 14 '19 at 7:24

• No. Consider K5+pendant and $K_5$. – LeechLattice May 14 '19 at 8:24
• got it! But, I believe, every induced even subgraph of a Class 1 graph has $\Delta-2$ 1-factors. Any counterexample to this? Sorry, if it is too chatty, but bear just this one time! – vidyarthi May 14 '19 at 8:32