Abstract Graphs

Prepared by:

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

email:

malkevitch@york.cuny.edu

web page:

http://www.york.cuny.edu/~malk/


One of the reasons the concept of a number is hard is that there is a difference between the concept of the number "seventy" and the ways one represents that number in a particular "base": So we can represent "seventy" as 70 base 10 and 1000110 base 2. And then there is the notion of what a base is to understand.

Technically, one might argue there is a difference between a graph as an abstraction and drawings of graphs. So, we have acted as if a graph is nothing more than drawings of dots and lines on a piece of paper (or white board). However, those who enjoy "abstraction" would say: A graph is a finite set V of objects called vertices and a subset E of unordered pairs of distinct elements of V (the edges) of the graph. With this approach we banish multiple edges and loops, but with care one can correct that. So V = {1, 2, 3, 4, 5} and E = { 12, 13, 14, 15, 34, 24 } where we don't distinguish between 12 and 21, 13 and 31, etc. in a graph.

Exercise: Draw a "picture" of this graph.

Often pictures speak louder than symbols.

When one draws graphs on a piece of paper some, edges may meet at points other than vertices. Thus, if one draws the complete graph on 6 vertices, one can't help having "accidental crossings." Note that if a graph has no loops or multiple edges it is possible to give drawings in the plane that avoid curved connections between the vertices, In particular this can be done for plane graphs, and this fact is sometimes called Fary's Theorem. Fary was a Hungarian mathematician and he proved this in 1948 but others showed the same result independently. Remember that when one draws graphs one has the "freedom" to decide where to place the vertices and the (Euclidean) lengths of the edges (which leads to a variety of unsolved problems).

One could "represent" graphs by dots and line segments in 3-dimensional space. Now, all graphs have the property that they can be represented by points and line segments where edges meet only at vertices. However, this is not very convenient compared to thinking of graphs as drawings in the plane, so that is what we typically do. But there are issues of "knotted" embeddings and "unknotted" embeddings of graphs in 3-dimensions. Yes, graph theory, like all mathematics, requires new definitions, tools, and concepts to make the progress that it has in understanding geometric phenomena. But people have barely scratched the surface of what can be done by using the "power" implicit in the theorem: A connected plane graph obeys: V+F-E=2!! And shortly we will get to the amazing theorem of Ernst Steinitz: G is the vertex-edge graph of some 3-dimensional convex polyhedron if and only if it is planar and 3-connected.

Soon we will look at some more geometric aspects of polygons and planar graphs. We also look at trees in more detail, and show that we can give a proof using mathematical induction of the important fact about trees: V = E + 1. Do you think the converse of what we showed is true: If V = E + 1 for a graph must the graph be a tree?