Logical Graphs • Discussion 8
•
https://inquiryintoinquiry.com/2023/10/02/logical-graphs-discussion-8/
Re: Logical Graphs • Formal Development
•
https://inquiryintoinquiry.com/2023/09/01/logical-graphs-formal-development…
Re: Laws of Form • Alex Shkotin
•
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