# Graph Theory à la Frank Harary

Updated: 6 days ago

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

**(which consists of only triangles).**

*Cactus*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 w**e'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

**a vertex that is distance at most 2 away from any other vertex. For how many of non-isomorphic tournaments there are, see**

*king:*__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**