Frank Harary was an amazing graph theorist who spread the love of his field far and wide, so I wanted to spend some time talking about his ideas, achievements, and interactions with other mathematicians of the time. This was inspired by picking up his aptly-named book Graph Theory (1969) from JMU's Rose Library (which has an amazing selection of math books). I'll start by including the scanned cover of his book and his dedication page:
"To Kasimir Kuratowski, who gave K5 and K3,3 to those who thought planarity was nothing but topology" - What a lovely sentence! This is in reference to the foundational theorem of Kuratowski in the area of Forbidden Graph Characterizations, which states that a graph is planar if and only if it does not contain one of the two graphs pictured above.
EDIT: A wonderful exposition of the history behind the above sentence was graciously brought to my attention by Gary Chartrand: A Tale of Two Graphs. This is one of many writings that he has co-authored with Ping Zhang at Western Michigan University.
Frank Harary was born on March 11, 1921 in New York City, the oldest son of Jewish immigrants. He passed away in 2005, and before discussing his mathematics, I want to share a paragraph from his obituary:
Frank had a beautiful spirit! He had a great j'oie de vivre which overflowed naturally and spontaneously. He had a sweet heart and gentle disposition. He had a deep and abiding love for his mathematics. He was a free spirit, who walked to the beat of a different drummer. He loved the arts and attended theater and concert performances with great appreciation. He was fun loving, had a great sense of humor and was a delight to be around.
I admire him greatly for the way he shared his love of mathematics with the world. He was well-known to turn mathematical theorems into games to make them more accessible. An example I have copied myself is to take the complete graph on 6 vertices and play a game where two players take turns coloring edges Red or Blue, with the goal of making a triangle in your color. In essence, it's a more mathematical Connect 4. Since the Ramsey Number R(3,3) is equal to 6, the game is guaranteed to end with a winner.
By 1945, Harary had gotten his bachelor's and master's degree from Brooklyn College. He also spent a year at Princeton University studying theoretical physics and a year at New York University studying applied math. But for his PhD, his interests had turned heavily to pure math and he began to work on a doctorate in mathematical logic under Alfred Foster at the University of California, Berkeley. Foster had just published his paper "The Theory of Boolean-Like Rings", in which he gives various characterizations of Boolean-Like Rings, discusses a certain duality for such rings, and then gives a structure theorem. Let's write one of his characterizations (Thm 19) on Boolean-Like rings here:
Theorem 19 (Foster): A ring R is Boolean-Like if and only if
It is commutative, with unit element.
It is of characteristic 2.
Each element may be expressed as a sum of an idempotent and a nilpotent element.
The equation nm = 0 holds for all nilpotent elements n,m of R.
Frank Harary expanded on this with his PhD thesis "The Structure of Boolean-Like Rings", but the paper (1950) that eventually came from this work was not his first published paper. Instead, his first published paper (1949) was entitled "On The Algebraic Structure of Knots", inspired by a Colloquium address by Herbert Seifert. How incredible that must have been!
A quick aside: Although my love of Knot Theory began with my mentor Laura Taalman, Seifert's work has always been a main interest point of mine. During my first research project in 2014 on Knot Theory, we 3D-Printed various knots in their usual comformation and then in some other conformation designed to demonstrate a knot invariant. One of the things I did was 3D-Print a Seifert Surface using the amazing software SeifertView designed by Jack van Wijk. And I hope to one day recreate the algorithm to form Seifert Surfaces from knots in Blender or some other 3D-Modeling software.
NOTE: The usual SeifertView does not allow exports, but Jack van Wijk was kind enough to email me an experimental version that allowed for exports. If you'd like a copy, please email me at jonathan@jmathg.com or jonathanmgerhard@gmail.com.
Frank Harary then became a research assistant at the Institute For Social Research at the University of Michigan and eventually a full professor at U-M. Following his list of publications, you can see him applying Graph Theory to many fields outside mathematics. In 1952, he uses the relationship between matrix powers and paths in graphs to study sociometry.
In 1953, he published "Graph Theory as a Mathematical Model in Social Science" and in 1954, he published a paper on communication networks in the Journal of Social Psychology. Throughout the years, he went on to publish papers applying graph theory to
Management Sciences,
Behavioral Sciences,
Language,
Sociology/Social Sciences,
Human Relations,
Anthropology
Operations Research,
Chemistry,
Physics,
just to name a few!
But while his breadth was impressive, what is truly incredible to me is how deep he dove into the mathematics of his field. He is known as a Founding Father of Graph Theory and was referred to as "Mr. Graph Theory" by friends and colleagues. And that is not without reason!
Frank Harary had a love of mathematics that he wanted to spread to the world, which pushed him to create the Journal of Combinatorial Theory with Gian-Carlo Rota in 1966. Wanting a deeper focus on graph theory, he created and built the Journal of Graph Theory from 1974 to 1977 as an offshoot of the Journal of Combinatorial Theory. The first issue contains welcoming notes by Paul Erdös, George Pólya, Paul Turán, and Edward Wright, and the journal continues to this day.
In 1978, Harary started the yearly graph theory conference MIGHTY, which has meant slightly different things as time has gone on - from the initial MIchigan GrapH TheorY to the current MIdwest GrapH TheorY. Throughout the years he has given countless lectures at universities all around the world (and even two high schools). He has without a doubt been a king of community outreach, but let's dive into the actual math now.
The Mathematics of Mr Graph Theory
Among his many achievements, Frank Harary was a master of counting. His first paper with such a goal was "On the Number of Husimi Trees" in 1953. A Husimi Tree is not necessarily a tree, but is a connected graph in which no edge lies on more than one cycle. For example, a Husimi Tree consisting of only edges is a Cayley Tree. Another example is the Cactus Graph, not to be confused with what Harary calls a Cactus (which consists of only triangles).
This result generalizes Cayley's Formula, which is usually phrased as counting labelled trees. For a graph G, if we write n_i as the number of i-cycles in G, then Harary gives the number of Husimi Trees of type (n_2, n_3, ..., n_p) as
He also contributed to the understanding of Polya Enumeration, which introduces group actions and cycle indices to count graphs up to isomorphism, which adds a layer of immense difficulty. A popular theme in this area being a sum of reciprocals, Harary even has an index named after him, defined to be the sum of reciprocals of distances between distinct vertices. As an example, if we take the complete graph K_n, then every vertex is connected, so the Harary Index is the sum of 1 for each edge, meaning it is simply the number of edges.
H(K_n) = (n choose 2)
He also applied his ideas to Otter's Tree Enumeration, which also employs formal power series but hinges on the concept of similarity under homeomorphism. An analogue of the Euler Characteristic, Otter showed that in any tree, the number of nonsimilar vertices minus the number of nonsimilar edges plus the number of symmetry lines is equal to 1. Therefore,
if we count the total number of nonsimilar vertices occurring among all trees with n vertices, subtract the total number of nonsimilar line segments (except symmetry lines) occurring among these trees, then each individual tree gives the contribution 1, so we get as result the total number of trees.
Harary's ability to count is amazing - here are a few of his counting papers through the years:
The number of complete cycles in a communication network (1954)
The number of linear, directed, rooted, and connected graphs (1955)
On the number of dissimilar line-subgraphs of a given graph (1956)
The number of oriented graphs (1957)
On the number of bicolored graphs (1958)
The number of functional digraphs (1959)
The number of homeomorphically irreducible trees, and other species (1959)
Unsolved problems in the enumeration of graphs (1960)
Enumeration of bicolourable graphs (1963)
The number of plane trees (1964)
Enumeration of self-converse digraphs (1966)
In fact, he even wrote a book on it! Along with Edgar Palmer, he wrote Graphical Enumeration in 1973. They discuss Polya's (and earlier yet unrecognized at the time, J. Howard Redfield's) technique for counting and show how they've used it to count various families of graphs.
Harary's work took him to collaborations with people like Stephen Hedetniemi, Geert Prins (both his doctoral students), William T. Tutte, Ronald C. Read, Václav Chvátal, Andreas Blass, Robert W. Robinson, Ron Graham, and Paul Erdős. Again, look through his publications to see the full extent of his collaborations. After I just looked through it some more, I see he wrote two papers (1983/1984) with Bruce Sagan, who was my mentor during my first REU at Michigan State University (and long afterwards!). Bruce was an incredible mentor, with us every single day, working directly alongside us and guiding us as we needed.
Beginning in 1971, Harary began a series of papers entitled "Generalized Ramsey Theory for Graphs" with Václav Chvátal. The basic Ramsey Number R(n,m) is defined to be the smallest integer so that any 2-coloring of the edges of the complete graph on R(n,m) vertices will contain some monochromatic copy of a complete graph (a clique) on n vertices in the first color or m vertices in the second color. A usual generalization is looking at R(n_1,n_2,...,n_k), where we allow coloring with k colors and look for a monochromatic n_i-clique in color i.
However, the direction Harary and Chvátal went encompassed both of these and so much more. They take a fixed graph G and a family of Forbidden Graphs we call F, and define R(G,F,c) to be the greatest integer so that any coloring of the edges of G with c colors will result in at least R(G,F,c) monochromatic copies of a member of F. They call these R-Numbers.
They give a few examples of topics in Graph Theory that are subsumed by studying these R-Numbers. If we take G = K_m and F = {K_n} to both be complete graphs, then R(K_m,K_n,2) as a function of m will tell us about the usual diagonal Ramsey Number R(n,n). If we're interested in the edge-chromatic number of a graph G, then we want to color the edges of G in such a way that no two incident edges are the same color. In other words, we just need to take F = {o--o--o} to be a path on 3 vertices.
Another example is the thickness of a graph G, which is defined to be the smallest number of planar graphs that the edges of G can be partitioned into. Remember Kuratowski's Theorem from the beginning of this post? It says that a graph is planar if and only if it does not contain a copy of K_5 or K_(3,3). So we just take F = {K_5, K_(3,3)} and we can get the thickness from the R-Number.
Their first theorem is a generalization of a technique of Erdős that relates the value of a certain series to the R-Number of a graph being 0. Their second theorem is about hypercubes specifically:
The Hypercube Graph Q_n is most succinctly (in my opinion) described as a graph whose vertices are all binary strings of length n, with two vertices connected if they differ in a single spot (their Hamming distance is 1).
So R(Q_n,Q_m,c) is looking at the hypercube Q_n, coloring its edges with c colors, and counting how many copies of monochromatic Q__m we can be sure we'll find. If m = 1, then Q_m is just a single edge, of which there are n2^(n-1) in Q_n, so no matter how many colors we choose, that is our R-Number.
On the flip side, if we just have a single color (meaning c = 1), then we're asking for how many copies of Q_m we're guaranteed to find within Q_n. This is a classic problem you'd likely encounter in any first course on Graph Theory! Thinking of each vertex as a binary string of length n, we choose m spots to act as the embedded copy of Q_m and with the remaining n-m spots, we have a free choice for whether they are 0 or 1. Each choice gives a different copy of Q_m, so we have a total of (n choose m)2^(n-m) copies of Q_m inside Q_n.
Ok, we're bouncing all around here, but that's not just my attention span - Frank Harary did so many things that it's easy to get distracted. But I couldn't possibly get as many down here as I want to. He worked in Group Theory and Toplogy and...well, all those areas we listed in the first section. What I want to focus on now is something that I have always loved since I started learning math - Mathematical Games!
Mathematical Games with Frank Harary
From 1981 to 1994, Frank Harary wrote 28 papers about mathematical games (also called combinatorial games). In the first such paper, he discusses achievement and avoidance games:
In these games, the rules must be formulated in such a way that the combined moves of the two players gradually construct the hypothesis of the theorem to be played. Hence one of the players must eventually be the first to reach the conclusion of the theorem. In an achievement game, he is the winner; in an avoidance game, the loser.
And here are a few of these papers so you can see what different topics he covered:
Achievement and avoidance games designed from theorems (1981)
Achievement and avoidance games for graphs (1982)
Achievement and avoidance games on finite configurations (1983)
Picasso animal achievement games/Latin square achievement games (1983)
Connect-it games (1984)
Arithmetic progression achievement and avoidance games (1985)
Geodetic games for graphs (1986)
Achievement and avoidance games for generating abelian groups (1987)
Kingmaker, Kingbreaker and the other games played on a tournament (1988)
Finite group table achievement games (1989)
Two graph-colouring games (1993)
Minimum degree games for graphs (1994)
Let's talk about some of these games!
A simple game surrounding graph coloring involves fixing a graph G and a number of colors k. Then two players A and B take turns coloring the vertices of a graph G while making sure we never color two adjacent vertices the same color. The game ends once we have no legal moves. The last to make a move is the winner or loser depending on if we're playing an achievement game or avoidance game respectively.
This game clearly ends since G only has a finite number of vertices. From a graph-theoretic perspective, our legal move condition forces us to always have a proper coloring of the vertices of G. In "Two Graph-Colouring Games", Harary and Zsolt Tuza tell us that the inspiration comes from this problem: For a given graph G = (V,E), a subset V' of V, a proper coloring C' of the subgraph G' induced by V', and an integer k, does there exist a proper coloring C of G with at most k colors so that the restriction of C to G' is equal to C'.
Now the question becomes: For a given G and k, who has the winning strategy, A or B? They answer this for a few classes of graphs and values of k.
At the end of the paper, they note that if k is larger than the maximum degree of G = (V,E), then the game will only terminate when all vertices are colored, which means achievement and avoidance winners depends only on the parity of |V|. They then isolate three particularly interesting situations:
k = maximum degree of G
k = chromatic number of G
k = 1
Although we might intuitively think k = 1 should be simple, if we think about it a bit, we see a relation to a very important concept in graph theory. If we only have a single color, then our legal move condition boils down to never coloring both endpoints of an edge. In other words, every colored vertex will be disconnected from every other one - so we have a maximal independent set inside G! Independent sets are studied in a variety of contexts - Ramsey Theory being a very popular one. Another example is Kőnig's Theorem, which relates maximum independent sets to minimal edge coverings.
Now let's see how he defines an achievement/avoidance game for Group Theory. We start with a group G and players A and B take turns removing elements x_i from G (meaning we don't allow repetition). At the end of turn k, we calculate G_k, the group generated by the elements {x_1, x_2, ..., x_k}. If G_k = G, then the game is over. They note that for a general group, determining the winner of this game is very difficult (who wants to play with the Monster Group?)
But they can in fact solve the problem for abelian groups! For the achievement game, the first case is easy: If G is cyclic, then A wins because A can just choose a generator of G. They then address 5 more cases, which are summarized as follows:
A wins if and only if G is cyclic or |V| is odd or
G = Z/2Z x Z/(2m+1)Z x Z/(4m + 2)Z
for m,k = 0,1,2,...
B wins otherwise.
For the avoidance game, they manage to deduce the winners in 4 cases. These are summarized with the following theorem:
A wins if and only if |V| is odd but G is nontrivial, or G = Z/(2k)Z with odd k.
B wins otherwise
Lastly, I won't go too deep into this, but I feel like I have to mention it! Martin Gardner is probably the first person most people think of when they think of recreational math. In 1997, Gardner published the book "The Last Recreations" which features a chapter entitled "Directed Graphs and Cannibals". In this chapter, he mentions a letter from Frank Harary in 1980 describing a game on tournaments called Kingmaker.
If you look at the list above of papers Harary wrote on games, we see he makes this game public with his 1988 paper "Kingmaker, Kingbreaker and the other games played on a tournament". This paper seems hard to find (for me at least), so Gardner's description of it (along with many many other examples) is incredibly helpful!
The theorem underlying this game is called The King Chicken Theorem. That link is by the guy that Gardner credits, Stephen Maurer, and contains a wonderful exposition of this theorem in the chicken-viewpoint, but I'll stick to the graph-theoretic language for now. A tournament is created by choosing a direction for each edge of a complete graph. The theorem states that every tournament will contain a king: a vertex that is distance at most 2 away from any other vertex. For how many of non-isomorphic tournaments there are, see OEIS A000568.
For a vertex v, we'll write N_o(v) or N_i(v) to be the out/in-neighborhood of v and write d_o(v) or d_i(v) to be the out/in-degree of v respectively. The theorem can be more constructively stated as: For a given tournament T, any vertex k with maximum out-degree d_o(k) will be a king.
The proof goes by contradiction: If k is not a king, then there is some vertex c whose distance from k is larger than 2. Not being distance 1 from k means c is not in N_o(k). Not being distance 2 from k means that no vertex in N_o(k) has an outgoing edge to c, which means c has an outgoing edge into every vertex in N_o(k). But this means N_o(c) contains all of N_o(k) and k itself, so d_o(c) > d_o(k), contradicting the fact that d_o(k) was maximum. Therefore, k must be a king.
The game Harary designed from this theorem starts with an undirected complete graph. Players then take turns choosing edges and giving them directions. The first player to create a king wins (in Kingmaker) or loses (in Kingbreaker).
How wonderful it must have been to interact with such an enthusiastic and brilliant graph theorist! How could you not want to focus on some good old BGT (Beautiful Graph Theory) after learning about the deep passion Frank Harary held for it?
Resources Not Previously Linked:
https://www.cs.nmsu.edu/fnh/ (His homepage at NMSU)
Thank you for reading!
Jonathan M Gerhard