Chapter 19: A Theory of Graphs A graph is a collection of points connected by lines, similar to a map of cities connected by roads. Although simple, graph theory has wide applications in modeling various real-world situations. For example, planar graphs, which do not have crossing lines, are important in designing computer chips and electronic circuits. Additionally, graph theory helps solve puzzles and games. Graph theory also presents intriguing questions that are easy to state but difficult to answer. For instance, determining the minimum number of colors needed to color a map so that adjacent countries have different colors is a classic problem. A graph-theoretic proof that four colors are sufficient was published in 1879 but was later found to be incorrect. It took nearly a century to confirm that four colors are indeed enough. Some graph theory results involve algorithms to construct objects, such as paths between vertices. This chapter includes several such algorithms. Section 19.1 discusses three types of graphs: directed graphs (digraphs), undirected graphs, and multigraphs. A directed graph is defined by a set of vertices and a binary relation on the vertices, where each element of the relation is an edge. Directed graphs are typically represented with arrows indicating direction. A self-loop is an edge from a vertex to itself, and a loop-free graph has no self-loops. Undirected graphs have edges that are unordered pairs. If a digraph has a symmetric relation, it can be converted into an undirected graph by replacing pairs of arrows with undirected lines between vertices. This establishes a one-to-one correspondence between undirected graphs and digraphs with symmetric relations.Chapter 19: A Theory of Graphs A graph is a collection of points connected by lines, similar to a map of cities connected by roads. Although simple, graph theory has wide applications in modeling various real-world situations. For example, planar graphs, which do not have crossing lines, are important in designing computer chips and electronic circuits. Additionally, graph theory helps solve puzzles and games. Graph theory also presents intriguing questions that are easy to state but difficult to answer. For instance, determining the minimum number of colors needed to color a map so that adjacent countries have different colors is a classic problem. A graph-theoretic proof that four colors are sufficient was published in 1879 but was later found to be incorrect. It took nearly a century to confirm that four colors are indeed enough. Some graph theory results involve algorithms to construct objects, such as paths between vertices. This chapter includes several such algorithms. Section 19.1 discusses three types of graphs: directed graphs (digraphs), undirected graphs, and multigraphs. A directed graph is defined by a set of vertices and a binary relation on the vertices, where each element of the relation is an edge. Directed graphs are typically represented with arrows indicating direction. A self-loop is an edge from a vertex to itself, and a loop-free graph has no self-loops. Undirected graphs have edges that are unordered pairs. If a digraph has a symmetric relation, it can be converted into an undirected graph by replacing pairs of arrows with undirected lines between vertices. This establishes a one-to-one correspondence between undirected graphs and digraphs with symmetric relations.