Re: Logical Graphs • Formal Development
Re: Laws of Form • Alex Shkotin

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 in accord with the level of abstraction required by 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.

A graph consists of a finite nonempty set of points together with a prescribed set of unordered pairs of distinct points of   Each pair of points in is a line of and is said to join and   We write and say that and are adjacent points (sometimes denoted );  point and line are incident with each other, as are and   If two distinct lines and are incident with a common point, then they are adjacent lines.  A graph with points and lines is called a graph.  The 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 — except for the notion of painted graphs where I had to invent a new term due to 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.

cc: FB | Logical Graphs • Laws of Form • Mathstodon • Academia.edu
cc: Conceptual Graphs • Cybernetics • Structural Modeling • Systems Science