On the chromatic index of almost all graphs (Q1246431): Difference between revisions

To say that ``almost all graphs have a given property'' means that if \(P(n)\) is the probability that a random graph on \(n\) vertices has that property, then \(P(n)\to 1\) as \(n\to\infty\).It is known that the chromatic index of a simple graph G is either \(\rho\) or \(\rho+1\) where \(\rho\) is the maximum vertex-degree of \(G\) (Vizing's theorem). The second author conjectured that almost all graphs have the chromatic index equal to \(\rho\). The purpose of this paper is to prove the conjecture. The result is deduced from the lemma that almost all graphs have a unique vertex of maximum degree.