Três teoremas interessantes em teoria dos grafos

Abstract

The results presented in this work constitute themselves in particular topics of Graph Theory. One of the great advantages of the study of graphs lies in the fact that, besides being mathematically interesting objects, graphs appear in a multitude of practical ap- plications. Indeed, on the one hand, the statements of most of the famous problems in Graph Theory can be easily explained to an average high school student; on the other, the roots of those problems, most of the times, lie in important practical applications of the theory to such diverse areas as Physics, Chemistry, Biology, Electrical Engineering and Operations Research. In this work we restrict ourselves to the discussion of the spe- cific problems in Graph Theory: the Five Colors Theorem, which is a problem on vertex coloring of planar graphs, the Art Gallery Theorem, which is a result on Extremal Graph Theory, and the Friedship Theorm, which is an amazingly beautiful result in Algebraic Graph Theory. We present a structured and detailed discussion of such results, in the hope that their aesthetic appeal serve as an exhortation for the inclusion of the rudiments of Graph Theory in High School curriculum.