Introduction to Graph Theory,Sections 6.1-6.3,3/1/2004,Discrete Mathematics for Teachers, UT Math 504, Lecture 08,2,Introduction,The three sections we are covering tonight have in common that they mostly contain definitions. Graph theory suffers from a large number of definitions that mathematicians use inconsistently. For instance, what some mathematicians call a graph, others call a simple graph. What some mathematicians call a multigraph, other just call a graph. Some mathematicians call a graph labeled if the vertices are labeled, while others mean that the edges are labeled.,3/1/2004,Discrete Mathematics for Teachers, UT Math 504, Lecture 08,3,Introduction,Why are the definitions so confused in graph theory? I suspect it is simply a matter of convenience. People who want to write about simple graphs make their lives easier by just calling them graphs. People who want to write about multigraphs call them graphs. The caveat in all of this is clear: when you start to read a new book on graph theory read the definitions carefully to make sure of the ground rules.,3/1/2004,Discrete Mathematics for Teachers, UT Math 504, Lecture 08,4,Graphs: Basic Definitions,A graph, G, comprises a set V of vertices and a set E of edges. The vertex set can be anything, but is most commonly a collection of letters or numbers. The set of edges is a set of doubleton subsets of V. That is Ea,b:a,bV and ab. We denote the graph by G(V,E). If G(V,E) is a graph and a,bE, then we say vertices a and b are adjacent and the edge a,b joins them or connects them or is incident on them. We call a and b the endpoints of the edge. Two edges that share one vertex, such as a,b and b,c with ac, are adjacent to each other.,3/1/2004,Discrete Mathematics for Teachers, UT Math 504, Lecture 08,5,Graphs: Representation,Normally we think of a graph as a drawing. A little reflection shows that the definition above is a formalization of this intuition about graphs. We think of a graph comprising dots (vertices) connected by line segments or curves (edges). We give every dot a label and form the vertex set V out of the labels. If there is a curve connecting dots a and b, we include the edge a,b in E.,3/1/2004,Discrete Mathematics for Teachers, UT Math 504, Lecture 08,6,Graphs: Examples,Let V=a,b,c,d and E=a,b,a,c,b,c,c,d,3/1/2004,Discrete Mathematics for Teachers, UT Math 504, Lecture 08,7,Graphs: Examples,Let V=a,b,c,d and E=a,b,a,c,a,d,b,c,b,d,c,d. This is called the complete graph on four vertices, denoted K4.,3/1/2004,Discrete Mathematics for Teachers, UT Math 504, Lecture 08,8,Graphs: Examples,Let V=a,b,c,d and E=.,3/1/2004,Discrete Mathematics for Teachers, UT Math 504, Lecture 08,9,Graphs: Variant Definitions,Our definition of graph does not allow an edge to join a vertex to itself. Such an edge is called a loop, and some definitions of graph allow them. Our text refers to such a structure as a graph with loops (clever, huh?), which is a straightforward name but not common as far as I know. Some definitions of graph allow for multiple edges between the same two vertices. Our book calls this structure a multigraph (which is a common and helpful usage in that it makes E a multiset rather than a set). Our book calls a multigraph with loops a pseudograph. I think this terminology may be standard, but I am not a graph theorist.,3/1/2004,Discrete Mathematics for Teachers, UT Math 504, Lecture 08,10,Graphs: History,Texts typically trace the origin of graph theory to the Knigsberg Bridge Problem and its solution by Leonhard Euler (the book gives this solution a date of 1736). The book describes the problem and the history behind it. You may recall that Euler (pronounced “oiler”) was a brilliant mathematician and perhaps the most prolific of history, remaining productive into his 70s or 80s despite going blind.,3/1/2004,Discrete Mathematics for Teachers, UT Math 504, Lecture 08,11,Graphs: Applications,On p. 229 the book mentions the application of graphs to printed circuit and microchip design. Graphs seem an intuitively natural way to model many situations in the Creation (connections of wires/leads, logistics/transportation problems, pipelines between points with known capacities, family trees, organizational charts, among many more). This suggests why graph theory has grown so dramatically in the past century.,3/1/2004,Discrete Mathematics for Teachers, UT Math 504, Lecture 08,12,Graphs: More Definitions,The degree of a vertex is the number of edges incident on the vertex. That is, if G(V,E) is a graph and aV, then degree(a)=|x:a,xE|. Put another way, the degree of a vertex is the number of vertices adjacent to it. If a vertex has no adjacent vertices (degree 0), then it is isolated.,3/1/2004,Discrete Mathematics for Teachers, UT Math 504, Lecture 08,13,Graphs: Theorems on Degree,(6.7) The sum of the degrees of the vertices of a graph is even. Proof: Each edge joins two vertices. Thus adding up the degrees of the vertices is equivalent to counting all the edges twice. Therefore the sum of the degrees is even. In fact it is twice the number of edges. (6.8) Every graph has an even number of vertices of odd degree. Proof: Otherwise the sum of the degrees would be odd.,