Brief Introduction to Graph Theory

Prepared by:

Joseph Malkevitch
Department of Mathematics and Computer Studies
York College (CUNY)
Jamaica, New York

email:

malkevitch@york.cuny.edu

web page:

http://york.cuny.edu/~malk Theorem: The sum of the valences of the vertices of a graph equals twice the number of edges in the graph.

Graph theory provides a powerful tool for constructing mathematical models in a variety of situations. Given "objects" one can represent them by dots and the relationship between the objects can be indicated using straight or curved line segments. Dots might represent people, street corners, or books. Line segments could indicate that the people are friends, that street corners are connected by a street, or that the books have the same author. In a graph edges don't have any direction but in a digraph (short for directed graph) one can use directed line segments (segments with arrows) to indicate, say, the direction that traffic can travel in down a street. The figure below (from Wikipedia) shows a digraph with 4 vertices and 5 directed edges. The numbers shown indicate invalence (indegree) and outvalence (outdegree), first the number edges into the vertex, and then separated by a comma the number of edges out of the vertex. Theorem: The sum of the indegrees equals the sum of the outdegrees and both of these quantities give the number of directed edges in the graph.

A digraph can represent the results of a round robin tournament where each pair of teams (each team represented by a dot) plays one game against each other team, and ties are not possible. Each pair of teams is joined by a directed edge indicating which team beat the other. The indegree and outdegres of a vertex count the number games a team lost and won. A directed edge from vertex A to vertex B in this "tournament" context means that A beats B. (In the figure, 3 players; each with one win and one loss.) 