ABSTRACT
This chapter focuses more keenly on properties of graphs, starting with connectivity. It considers whether or not a graph contains certain special circuits. Euler circuits are those that traverse every edge exactly once. Hamiltonian cycles hit every vertex exactly once. The determination of whether or not a graph is planar is important in circuit design. The chapter builds up to one of the most famous theorems in graph theory and mathematics in general, the Four-Color Theorem. It determines which graphs can be drawn in the plane without edge crossings. The chapter also considers the general problem of determining the minimum number of colors needed to color the vertices of a graph so that neighbors have different colors. It discusses a significant result on planar graphs known as the Four-Color Theorem. The chapter explores the relationship between the chromatic number and the maximum degree of a graph.
