Logical Graphs • Discussion 8
•
https://inquiryintoinquiry.com/2023/10/02/logical-graphs-discussion-8/
•
https://groups.io/g/lawsofform/message/2468
Hi Alex,
I got my first brush with graph theory in a course on the Foundations of Mathematics Frank Harary taught at the
University of Michigan in 1970. Frank was the don, founder, mover, and shaker of what we affectionately called the
“MiGhTy” school of graph theory, spawned at U of M, Michigan State, Illinois, Indiana, and eventually spreading to other
hotbeds of research in the Midwest and beyond. Later I took my first graduate course in graph theory from Ed Palmer at
Michigan State, using Harary's “Graph Theory” as the text of choice.
Definitions of graphs vary in style and substance according to the level of abstraction befitting a particular approach
or application. The following is a classic formulation, one which covers the essential ideas in a very short space, and
one whose elegance and power I've come to appreciate more and more as time goes by.
Harary (1969):
❝A “graph” G consists of a finite nonempty set V = V(G) of p “points” together with a prescribed set X of q unordered
pairs of distinct points of V. Each pair x = {u, v} of points in X is a “line” of G, and x is said to “join” u and v.
We write x = uv and say that u and v are “adjacent points” (sometimes denoted u adj v); point u and line x are
“incident” with each other, as are v and x. If two distinct lines x and y are incident with a common point, then they
are “adjacent lines”. A graph with p points and q lines is called a (p, q) graph. The (1, 0) graph is “trivial”.❞
(Harary, Graph Theory, p. 9).
I'll be hewing fairly close to that definition and terminology, though most graph theorists are used to the more common
variations, like “nodes” instead of “points” and “edges” instead of “lines” — all but for the notion of “painted graphs”
where I had to invent a new term on account of the fact that “labels” and “colors” were already taken for other uses.
References —
• Harary, F. (1969), Graph Theory, Addison-Wesley, Reading, MA.
• Harary, F., and Palmer, E.M. (1973), Graphical Enumeration, Academic Press, New York, NY.
• Palmer, E.M. (1985), Graphical Evolution : An Introduction to the Theory of Random Graphs, John Wiley and Sons, New
York, NY.
Regards,
Jon