Brief Introduction to Graph Theory (2017)

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

The graph has three 1-valent vertices. Vertices of degree 1 are often called leaves by computer science scholars and biologists interested in graph theory.

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.

When a digraph represents the results of a round robin tournament (each pair of teams plays one game against each other team) where ties are not possible (every pair of teams is joined by a directed edge indicating which team beat the other) the indegree and outdegree of a vertex count the number games a team won and lost.

Theorem:

In any graph the sum of the degrees adds to twice the number of edges in the graph.

Corollary: The number of vertices of odd valence in a graph is an even number