(1) doesn't hold, then we can interchange the colors and on the -path and set the color of to be , thus creating a proper -edge-coloring of from . The other way around, if a proper -edge-coloring exists, then we can delete , restrict the coloring and (1) won't hold either. Now, let and be a proper -edge-coloring of and be missing in with respect to . We define to be a maximal sequence of neighbours of such that is missing in with respect to for all . We define colorings as for all , not defined, otherwise. Then is a proper -edge-coloring of due to definition of . Also, note that the missing colors in are the same with respect to for all . Let be the color missing in with respect to , then is also missing in with respect to for all . Note that cannot be missing in , otherwise we could easily extend , therefore an edge with color is incident to for all . From the maximality of , there exists such that . From the definition of this holds: Let be the -path from with respect to . From (1), has to end in . But is missing in , so it has to end with an edge of color . Therefore, the last edge of is . Now, let be the -path from with respect to . Since is uniquely determined and the inner edges of are not changed in , the path uses the same edges as in reverse order and visits . The edge leading to clearly has color . But is missing in , so ends in . Which is a contradiction with (1) above. Classification of graphs Several authors have provided additional conditions that classify some graphs as being of class one or class two, but do not provide a complete classification. For instance, if the vertices of the maximum degree in a graph form an independent set, or more generally if the induced subgraph for this set of vertices is a forest, then must be of class one. showed that almost all graphs are of class one. That is, in the Erdős–Rényi model of random graphs, in which all -vertex graphs are equally likely, let be the probability that an -vertex graph drawn from this distribution is of class one; then approaches one in the limit as