6.042/18.] Mathematics for Computer Science March 1. 2005 Srini devadas and Eric Lehman Lecture notes Graph Theory 1 Introduction normally, a graph is a bunch of dots connected by lines. Here is an example of a graph B H D A F E Sadly, this definition is not precise enough for mathematical discussion. Formally, a graph is a pair of sets(V, E), where v is a nonempty set whose elements are called vertices E is a collection of two-element subsets of V called edges The vertices correspond to the dots in the picture, and the edges correspond to the lines Thus, the dots-and-lines diagram above is a pictorial representation of the graph(V,e whe V=A, B,C, D,E, F, G, H, II E={{A,B},{A,C},{B,D},{C,D},{C,E},{E,F},{E,G},{H,I}} 1.1 Definitions A nuisance in first learning graph theory is that there are so many definitions. They all correspond to intuitive ideas, but can take a while to absorb. Some ideas have multi- le names. For example, graphs are sometimes called networks, vertices are sometimes called nodes, and edges are sometimes called arcs. Even worse no one can agree on the exact meanings of terms. For example, in our definition, every graph must have at least one vertex. However, other authors permit graphs with no vertices. (The graph with6.042/18.062J Mathematics for Computer Science March 1, 2005 Srini Devadas and Eric Lehman Lecture Notes Graph Theory 1 Introduction Informally, a graph is a bunch of dots connected by lines. Here is an example of a graph: A B C D E F G H I Sadly, this definition is not precise enough for mathematical discussion. Formally, a graph is a pair of sets (V, E), where: • V is a nonempty set whose elements are called vertices. • E is a collection of two­element subsets of V called edges. The vertices correspond to the dots in the picture, and the edges correspond to the lines. Thus, the dots­and­lines diagram above is a pictorial representation of the graph (V, E) where: V = {A, B, C, D, E, F, G, H, I} E = {{A, B} , {A, C} , {B, D} , {C, D} , {C, E} , {E, F} , {E, G} , {H, I}} . 1.1 Definitions A nuisance in first learning graph theory is that there are so many definitions. They all correspond to intuitive ideas, but can take a while to absorb. Some ideas have multi￾ple names. For example, graphs are sometimes called networks, vertices are sometimes called nodes, and edges are sometimes called arcs. Even worse, no one can agree on the exact meanings of terms. For example, in our definition, every graph must have at least one vertex. However, other authors permit graphs with no vertices. (The graph with