THE HILTON{ZHAO CONJECTURE IS TRUE FOR GRAPHS WITH MAXIMUM DEGREE 4.

A simple graph G is overfull if jE(G)j > bjV (G)j=2c. By the pigeonhole principle, every overfull graph G has 0(G) > . The core of a graph, denoted G, is the subgraph induced by its vertices of degree . Vizing's adjacency lemma implies that if 0(G) >, then G contains cycles. Hilton and Zhao conjectured that if G is connected with 4 and G has maximum degree 2, then 0(G) > precisely when G is overfull. We prove this conjecture for the case = 4. [ABSTRACT FROM AUTHOR]