home | index | units | counting | geometry | algebra | trigonometry & functions | calculus
analysis | sets & logic | number theory | recreational | misc | nomenclature & history | physics

Final Answers
© 2000-2017   Gérard P. Michon, Ph.D.

Graph Theory

Lisez Euler, lisez Euler !
 C'est notre maître à tous.

Pierre-Simon Laplace (1749-1827)

Related articles on this site:

Related Links (Outside this Site)

Graph Theory  by  Reinhard Diestel  (pdf, 1997, 2000, 2005).
Graph and Digraph Glossary  by  Bill Cherowitzo

Wikipedia :   Tensor product of graphs   |   Petersen graph


Graph Theory

 Leonhard Euler 
 (1707-1783) (2009-07-16)   The Seven Bridges of Königsberg
The puzzle that begat  graph theory.  Solved by Euler in 1735.

The martyred town of Königsberg was renamed Kaliningrad in 1946, in honor of Mikhail Ivanovich Kalinin (1875-1946).  The town and its surroundings had been attributed to the USSR at the Postdam Conference in 1945, as the Allies split that part of Europe among themselves.  Kaliningrad is now in a Russian enclave between Poland and Lithuania.  It is home to about  430,000  people.

The town has a long history;  Its fortress was founded in 1255 by the Teutonic Knights.  Königsberg joined the Hanseatic League in 1340 and it was the residence of the dukes of Prussia from 1525 to 1618.  Immanuel Kant (1724-1804)  was born there and never lived elsewhere.

 The 7 Bridges of Koenigsberg 
 in 1651

When Leonhard Euler (1707-1783)  visited the town, there were  seven  bridges over the  Pregel  river in Königsberg  (five of them connected the  Kneiphof  island to both banks and to the larger island upriver).  Legend has it that residents amused themselves by looking for a path which would cross each bridge once and only once.  As Euler couldn't meet that challenge, he set out to prove that there was no such thing and presented his formal result to the members of the  Saint Petersburg Academy  on August 26, 1735.

In the process, Euler founded  graph theory  and established its earliest nontrivial result in the form of a simple necessary and sufficient condition for the existence of the type of path the inhabitants of Königsberg were after.  Such a path is now called an  Eulerian path,  an  Eulerian trail,  an  Euler walk   or an  Euler chain  (it is called an  Eulerian circuit  if it ends where it started, which is  not  required in the original Königsberg puzzle).

   Koenigsberg Bridges Graph

Euler reduced the data to its bare essentials, although his original drawings were far from the modern picture at right, where each land mass is represented by a single numbered dot  (dubbed  vertex  or  node).  Each bridge is represented by a line  (a so-called  edge)  connecting a pair of dots.

The two vertices connected by an edge are the  extremities  of that edge.  Several edges may have the same extremities.

The object we just described is called an  undirected graph.  A generalized abstract definition is given below which views an  undirected graph  as a special case of a  directed graph, uniquely specified by its  adjacency matrix.  The elementary concept introduced by Euler in 1735 corresponds only to symmetrical matrices whose components are all nonnegative integers  (the "number of edges" from node i to node j or, symmetrically, from node j to node i).

In such an  undirected graph, the  degree  of a node is the total number of edges which have that node as one of their extremities  (for  directed graphs,  we would distinguish the origin and the destination of each edge and tally the former total as the  outdegree  of a given node and the latter total as its  indegree).

A graph in which there is an Eulerian circuit is said to be  Eulerian.  When there's an  Eulerian path  but no Eulerian circuit, then the graph is called  semi-Eulerian.

In 1735, Euler showed that every node in an undirected Eulerian graph has even degree.  (HINT:  As we walk through an Eulerian circuit, we arrive at a given node as many times as we leave it, using a different edge each time.)

Similarly, a semi-Eulerian graph only has two nodes with an odd degree  (HINT:  Those two nodes must be the endpoints of any Eulerian path.)

All  4  nodes of the above Königsberg graph have an odd degree.  Therefore, there's no Eulerian path through the bridges of Königsberg.  (Incidentally, deleting or adding a bridge  anywhere  makes the puzzle solvable.)

 A Semi-Eulerian Graph   By contrast, the graph at left is semi-Eulerian.  If you start at one of the two nodes of odd degree and keep moving along a new [unvisited] edge, then you  will  visit each edge exactly once and end up at the other odd node!

In general, to walk an Eulerian tour (if at all possible) you must use what's known as  Fleury's algorithm (1883) :  Always move along an edge whose removal from the set of unvisited edges will leave that set connected.

More precisely, it's the  edges  which must all be connected together; an Eulerian or semi-Eulerian graph may include any number of irrelevant  isolated  nodes which are not connected to any edge:

An Eulerian path exist in an undirected graph if and only if
no more than  2  nodes have an odd degree and
all the nodes of nonzero degrees are connected.

To solve the  Königsberg puzzle in 1735, Euler only needed to prove the above conditions to be  necessary.  He only conjectured them to be  sufficient.

Although a proof of the converse result  [by induction on the number of edges]  looks fairly straightforward, it seems that no such proof appeared in print before the posthumous publication (in 1873) of the argument devised by Carl Hierholzer (1840-1871) shortly before his death.

 Kaliningrad, on April 29, 2007 
 Courtesy of Google Earth. (c) Copyright 2009. Google, Inc.
The 9 or 10 Bridges of Kaliningrad   (Courtesy of Google Earth, 2007)   © 2009  Google
Five of the modern bridges of Kaliningrad are at or near the location of one of the seven historical Königsberg bridges discussed above.

Wikipedia :   Seven Bridges of Königsberg   |   Eulerian path
Euler and the Bridges of Königsberg  by  Thomas M. Green
Euler and Königsberg's Bridges:  A Historical View  by  Gerald L. Alexanderson  (AMS, 2006)
The Euler-Hierholzer Theorem  by  Robin Whitty  (Theorem of the Day)
Video :   The Seven Bridges of Königsberg  by  Cliff Stoll  (Numberphile, 2016-11-02).

(2009-01-14)   Undirected Graphs
A special type of  directed  graphs.

An undirected graph is just a directed graph  (or  digraph)  whose adjacency matrix  A  is symmetrical.

The Königsberg graph  (shown at right)  is one example.

 Koenigsberg Bridges Graph A   =     bracket

In the (unusual) generalization of digraphs which features adjacency matrices whose elements are complex numbers  (instead of being limited to nonnegative integers)  an undirected graph is best defined as a  self-adjoint  digraph  (i.e., a digraph whose  adjacency matrix  is Hermitian).

(2008-06-26)   Adjacency Matrix
A concept which is usefully generalized beyond ordinary graphs.

A  directed graph  (or  digraph)  is a set of nodes connected by directed edges.  In a  simple  digraph, there's  at most one  such edge from one node to the other  (for non-simple digraphs, there can be several).

Some authors do not allow  loops  (edges which go from one node to itself)  in a  simple  undirected graph.  I beg to differ.

A digraph,  simple or not,  is fully specified by its so-called  adjacency matrix  whose element  aij  is equal to the number of edges going from node  i  to node  j.  The adjacency matrix of a  simple  digraph has  Boolean  elements  (0 or 1).

Normally, the adjacency matrix of a digraph is a square matrix of nonnegative integers.  However, we may also usefully consider  rectangular  matrices  in the case of  bipartite graphs  where the departure nodes and arrival nodes of the edges are from disjoint sets.

Incidentally,  a bipartite graph  is also a special type of  undirected  graph whose nodes can be divided into two disjoint sets U and V such that every [undirected] edge of the graph connects one node of U to one node of V.  Either viewpoint defines in terms of graphs a structure isomorphic to the  relations  between U and V  (fundamentally, a  relation  is a subset of the Cartesian product U´V).

Also, egdes could be labeled with additive  amplitudes  different from 0 or 1.  If several edges [having the same origin and target] are equated with a single edge carrying an amplitude equal to the sum of their amplitude,  we obtain a mathematical structure isomorphic to the unrestricted matrices over the set of amplitudes.  Amplitudes can be real or complex numbers, or any other type of quantity for which addition and multiplication are well-defined  (cf. quantum mechanics).

The digraph (or the bipartite graph) whose adjacency matrix is the  product of two adjacency matrices turns is simply the digraph in which tere are as many edges from node i to node j as there are ways to go from i to j using one edge of the first graph [to go from i to any node k] and one edge of the second [to go from k to j].

Indeed, if there are  aik  ways to go from i to k and bkj  ways to go from k to j, then the number of ways to go from i to j via all possible nodes k is given by the following formula, which is also how the relevant element in the product of the adjacency matrices is computed:

å k   aik  bkj

Applying this remark iteratively, we see that the matrix  An  is the adjacency matrix of a digraph which has as many edges from i to j as there are paths from i to j consisting of n edges of the graph whose adjacency matrix is  A.

This result was put to good use by  Max Alekseyev  in the solution, presented below, of an enumeration problem originally posed by  Philip Brocoum.

(2010-10-24)   The Three Utilities Problem
Providing 3 cottages with 3 utilities without crossing lines.

planar graph  is an undirected simple graph  (i.e., at most one undirected egde connects any pair of vertices)  which can be drawn on a plane  (or, equivalently, on the surface of a sphere)  without crossing the lines associated to graph edges  (those lines connect the points associated to the graph vertices).

 Come back later, we're
 still working on this one...

Proof   (devised by Kazimierz Kuratowski  (1895-1980)  in 1930) :
The solution, if there was any, would provide a connected planar graph with  6  vertices and  9  edges to which the classical  Euler-Descartes formula would apply.  It would, therefore, feature  5  faces  (6-9+5 = 2).

Each of those  5  faces would have at least  4  edges  (since a triangular face would necessarily include a line connecting either two cottages or two utility providers, which is disallowed).  As each edge belongs to exactly two faces, this would imply the existence of at least  10  edges  (4 times the number of faces divided by 2).  Since we know that there are only  9  edges, no such solution graph can possibly exist.

Wikipedia :  Water, gas, and electricity

(2008-06-27)   Brocoum's Silent Circles
Screaming circles  enumerated by  Max Alekseyev.

On 2008-06-13,  Max Alekseyev  sent a complete outline of the following solution to the problem originally posed by Philip Brocoum, whereby it is asked in how many different ways  2n  people in a circle can avoid eye contact if they must look left, right, or directly across the circle.  (The names "screaming circles" and/or "silent circles" come from the fact that this activity has actually been practiced with the dramatic rule that two people who make eye contact must both  scream.)

There are 8 possible ways that two diametrically opposed people may gaze without looking at each other:    No eye contact.  No eye contact.  No eye contact.  No eye contact.  No eye contact.  No eye contact.  No eye contact.  No eye contact.

Let  G  be the digraph whose vertices are those  8  configurations,  where an edge from i to j indicates that, if the pair j is next to i in the counterclockwise direction, then eye contact occurs neither between the respective "top" members of pairs nor between the bottom members.  The  adjacency matrix  A  of the digraph G is:

  No eye contact.  No eye contact.  No eye contact.  No eye contact.  No eye contact.  No eye contact.  No eye contact.  No eye contact.
 No eye contact. 10111010
 No eye contact. 01111001
 No eye contact. 01111001
 No eye contact. 10111010
 No eye contact. 00111000
 No eye contact. 11111111
 No eye contact. 11111111
 No eye contact. 11111111

The 8 highlighted locations correspond to pairs of configurations obtained from each other by a  180° flip  (half-turn rotation).  A full  silent circle  of  2n  people  (n>1)  is equivalent to a path of n edges of G going from one node to its flipped counterpart.  The number of all such silent circles is thus the sum of all highlighted elements in the n-th power of the above adjacency matrix, starting with:


Now, the characteristic polynomial of the matrix A is:

det ( xI - A )   =   x ( x - 1 )  ( x 3 - 7 x 2 + 9 x - 1 )
=   x 4  ( x 4 - 8 x 3 + 16 x 2 - 10 x + 1 )

By the Cayley-Hamilton theoremA  is a root of the above polynomial.  Thus, the successive matrix elements at a given location in the n-th powers of  A  obey the following linear recurrence  (for n>3).  So does any sum of such elements.

an+4   =   8 an+3  -  16 an+2  +  10 an+1  -  an

In particular, the sum of the elements of  An  for the locations highlighted above obey this recurrence and the sequence is fully defined by stating that it starts with  2, 6, 30 and 156  (corresponding respectively to  n = 0, 1, 2, 3).

For  n = 0,  we're indeed dealing with 2 highlighted nonzero elements in the identity matrix  I.  For  n = 1,  we have  6  nonzero highlighted elements in  A.  The other two terms are from the sums of the relevant elements in the square and the cube of  A, as given above. 

The cases  n = 0  and  n = 1  are part of a valid basis for the solution sequence but are not relevant to Brocoum's original problem, which arguably starts with a circle of 4 people  (the above analysis is not valid for a "circle" of only two people):

That sequence  also  obeys a  third order  recurrence  (cf. A141385) :

an+3   =   7 an+2  -  9 an+1  +  an  -  2

30, 156, 826, 4406, 23562, 126104, 675074, 3614142, 19349430, 103593804, 554625898, 2969386478, 15897666066, 85113810056, 455687062274, 2439682811478, 13061709929934, 69930511268508, 374397872321626, 2004472214764742, 10731655163727066, 57455734085528408, 307609714339920002, 1646898048773411406, 8817254646440128230, 47206309800460114956, 252735774834033062026, 1353110890280530527806, 7244360568257876251362, 38785261740114392071304, 207650697956760388764674, 1111731890604551068962342, 5952052214361128375925630, 31866429183043699399583004, 170608266242660291482712698, 913412053265589874158667478, 4890276405858230195165841066, 26181834627859962790215592856, ...

Against my  feeble  advice, Alekseyev chose to put this sequence on record  (as A141221)  with a dubious start at  n = 1  with value 0  (to include the degenerate case of a "circle" of  2  people who have no choice but to look at each other).

Making Walks Count:  From Silent Circles to Hamiltonian Cycles   Max A. Alekseyev,  Gerard P. Michon  (2016-06-13).

 10 people arranged in 
 two facing circles of 5
(2008-06-28)   Silent Prisms
A screaming game for  short-sighted  people.

Before generalizing Brocoum's poser, let's present  another version  of the screaming game which can be analyzed with the  same  tools.

Consider a "prism" of 2n people:  They are arranged in two concentric circles so that each person in the inner circle faces directly a "partner" in the outer circle and vice-versa.  Each person is allowed to look at one of three people; either that "partner" on the other circle or one of the two neighbors on the  same  circle.

This screaming game accomodates short-sighted people, as each person will only look at nearby people, even with large circles.    Just a joke!   A slight variant would be to allow each player to look only at one of the three nearest people on the  other  circle.  Such rules merely yield a screaming game isomorphic either to Brocoum's circle  (if n is odd)  or to the same prism we're now discussing  (if n is even).

The problem of enumerating the number of ways 2n people can avoid eye contact under such rules can be dealt with exactly as above, with the  same digraph  G,  except that the nodes of  G  bear different labels, using the following  8 symbols associated with each pair of  partners.  The top of the symbol indicates what direction the partner in the  inner  circle is looking at  (right = counterclockwise)  whereas the bottom of the symbol tells about the parner in the  outer  circle.  (A vertical arrow thus indicates that one partner is looking at the other.  No symbols have two vertical arrows because partners can't look  silently  at each other).

 No eye contact.  No eye contact.  No eye contact.  No eye contact.  No eye contact.  No eye contact.  No eye contact.  No eye contact.

By convention, if  j  is in the location next to  i  in the   counterclockwise  direction,  then there's an edge from node  i  to node  j  in our digraph  G  iff  there no eye contact on either circle involving the two pairs of partners  This statement depends only on the node labels if we assume that each circle contains at least 3 people  (that's a more severe restriction than for the previous analysis, which remained perfectly valid even for  n = 2).  This yields the following adjacency matrix, where diagonal elements are now "highlighted" to indicate that a  silent solution  is a circuit of n edges from one node  back to itself  (no "flipping").

  No eye contact.  No eye contact.  No eye contact.  No eye contact.  No eye contact.  No eye contact.  No eye contact.  No eye contact.
 No eye contact. 10111010
 No eye contact. 01111001
 No eye contact. 01111001
 No eye contact. 10111010
 No eye contact. 00111000
 No eye contact. 11111111
 No eye contact. 11111111
 No eye contact. 11111111

This adjacency matrix is exactly the one we met before.  So, Alekseyev's recurrence holds between its successive powers  (at least beyond the fourth power)  and, therefore, between the sums of the highlighted elements, which are now actually the  traces  of those powers of  A,  namely  (A141384) :

8, 8, 32, 158, 828, 4408, 23564, 126106, 675076, 3614144, 19349432 ...
an+4   =   8 an+3  -  16 an+2  +  10 an+1  -  an

The recurrence, which was  a priori  guaranteed only for  n>3  happens to hold down to  n = 1  (it would hold for  n = 0  with a value of  4,  instead of 8).  So, we are slightly less  lucky  than in the previous case.  For  n > 0, an explicit formula is:

an   =   An + Bn + 1 + Cn     where:
A   =   5.3538557854308282...   =   ( 7 + 2 Ö22 cos u ) / 3
B   =   1.5235479602692093...   =   ( 7 - Ö22 cos u  + Ö66 sin u ) / 3
C   =   0.1225962542999624...   =   ( 7 - Ö22 cos u  - Ö66 sin u ) / 3
with   u  =  1/3  Arctg ( Ö5319 / 73 )
The sequence also obeys a simpler  third order  recurrence  (cf. A141385) :

an+3   =   7 an+2  -  9 an+1  +  an  +  2

As previously, the beginning of the sequence does not correspond to actual enumerations  (even more so, since the above is only valid if  n  is 3 or more).  The proper enumerations start with the numbers  158, 828 and 4408, which appear in that capacity within the more general discussion of the following section.

Note, in particular, that 4 people can be arranged in a proper screaming circle  (the corresponding graph is a tetrahedron, for which 30 of the 81 configurations are silent ones)  but not in a screaming prism, which requires at least 6 people  (as noted above, the value of  32,  which appears in the sequence of traces for  n = 2,  is irrelevant to screaming tallies).  2 people can't play any screaming game.

All told, with  2n  people, there are just two more silent configurations in a screaming game with a double circle (the above "prism" type) than in an ordinary game where "partners" are opposite each other in a single circle:

2n 4681012141618
 Single  30 156826440623562126104 6750743614142
 Double    158828440823564126106 6750763614144

(2007-03-19)   Brocoum's Poser Generalized
Markings of one edge per node in which no edge is marked twice.

There are  d  ways to mark only one edge at a node of degree d.  The total number of unrestricted markings is simply the product of the degrees of all nodes.  Among those, we want to enumerate the markings for which no edge is marked twice  (once at each of its extremities).

Philip Brocoum posed a special case of this problem (2007-03-10; e-mail) after pondering it for more than a year (2006-01-26).

One lesser generalization of Brocoum's poser is to consider  married people in a circle where no two spouses are neighbors, with the rule that one person may only look at a neighbor or a spouse  (Brocoum's original puzzle considered a circle of 10 people, with spouses always sitting at opposite locations across the circle).  We want to enumerate the scenarios where nobody makes eye contact.

In technical terms, this is a restriction of our general problem to undirected cubic Hamiltonian graphs  (namely, graphs where 3 edges meet at each node and which allow a circuit that goes through every node once and only once).

This class of graphs is complex enough to make questions about them about as difficult as they are for unrestricted graphs.

With 4 nodes, there's only one such graph  (the regular tetrahedron)  in which there are 30 different satisfactory markings  (out of 81 unrestricted possibilities). 

 4-people configuration.

With 6 nodes, Hamiltonian cubic graphs have 729 possible markings (36 ).  Two configurations lead to different numbers of satisfactory markings  (156 or 158).

 Two 6-people configurations.

With 8 nodes, there can be  826, 828, 834, 842 or 860 satisfactory markings.  (Two disjoint tetrahedra form a  disconnected  8-graph allowing 900 markings.)

 8-people configurations.

Note that the leftmost of the above graphs is isomorphic to the Brocoum case  (where two spouses are always in diametrically opposed positions).  To prove this, you may want to look for a Hamiltonian circuit besides the "obvious" outer circle and redraw the graph accordingly.  (Numbering the nodes helps!).

For the 17 Hamiltonian cubic graphs with 10 nodes, we obtain 17 different tallies of satisfactory markings:  4384, 4392, 4406, 4408, 4416, 4438, 4446, 4456, 4476, 4484, 4494, 4502, 4526, 4530, 4556, 4600 and 4602.

 10-people configurations.

Disconnected cubic graphs with 10 nodes allow either 4680 or 4740 markings  (30 tetrahedral configurations and either 156 or 158 for the other 6 nodes).  We're leaving out the only two connected cubic graphs with 10 nodes which are not Hamiltonian  (namely, the Petersen graph and the bridged graph   Cubic bridged graph 
 with 10 nodes  ).

 Hexagonal Prism Non-isomorphic graphs with the same tally exist, since the 80 Hamiltonian 12-node cubic graphs yield  only  75  tallies:

23248, 23256, 23294, 23310, 23348, 23356, 23358, 23372, 23376, 23404, 23412, 23436, 23450, 23466, 23468, 23522, 23562, 23564, 23592, 23608, 23616, 23626, 23644, 23654, 23662, 23710, 23718, 23726, 23734, 23772, 23788, 23816, 23842, 23868, 23878, 23904, 23922, 23930, 23950, 23968, 23972, 23976, 23984, 23992, 23994, 24022, 24032, 24038, 24076, 24078, 24094, 24108, 24130, 24144, 24164, 24190, 24222, 24226, 24236, 24272, 24274, 24318, 24356, 24380, 24382, 24470, 24516, 24578, 24588, 24598, 24628, 24632, 24640, 24848, 25200.

A trivial Hamiltonian circuit for an n-gonal prism  (a cubic graph with 2n nodes)  is obtained from a clockwise circuit of the top polygon and a counterclockwise circuit of the bottom polygon by replacing the two horizontal edges of one face with the two vertical edges of that face.

The numbers of  cubic graphs  with 2n nodes is given by the following sequence,  counting the empty graph  (n = 0)  but no 2-node graphs  (n = 1) :
1, 0, 1, 2, 6, 21, 94, 540, 4207, 42110, 516344, 7373924 ... (A005638).

The numbers of  connected cubic graphs  with 2n nodes are:
1, 0, 1, 2, 5, 19, 85, 509, 4060, 41301, 510489, 7319447 ... (A002851).

The numbers of Hamiltonian cubic graphs  with 2n nodes  are:
1, 0, 1, 2, 5, 17, 80, 474, 3841, 39635, 495991, 7170657 ... (A001186).

For very large numbers of nodes,  almost all cubic graphs are Hamiltonian  (a result established in 1992 by R.W. Robinson & N.C. Wormald).

Here are a few pretty representations of some  [Hamiltonian]  cubic graphs with the associated tallies of their numbers of silent configurations:

 Tetrahedron  Triangular Prism  Cube  Pentagonal Wedge
2n = 4 2n = 6 2n = 8
 Hexagonal Prism  Truncated Tetrahedron  Dodecahedron
2n = 12 2n = 20
 Truncated Cube  Truncated Octahedron
2n = 24

(2008-07-17)   Line Graph
A graph  L(G)  whose vertices are the edges of another graph  G.

Let  G  be a graph,  V  its set of vertices and  E  its set of edges.  The so-called  line-graph  of  G  is the graph  L(G)  whose set of vertices is  E  and whose edges connect all pairs of E which have one common extremity in G.

(2008-07-14)   Vertex Transitivity.  Edge Transitivity.
symmetric graph  is  both  vertex-transitive  and  edge-transitive.

graph automorphism  of a  simple  graph  G  is a bijection  f  of its vertices such that the image  f (e) = { f (i), f (j) }  of any edge  e = {i,j}  is always an edge.

A graph is said to be  vertex transitive  when, for any two of its vertices  i  and  j,  there is an automorphism which maps  i  into  j.

A simple graph is said to be  edge transitive  when, for any two of its edges u  and  v,  there is an automorphism which maps  u  into  v.

A simple graph is  symmetric  when it's both vertex-transitive and edge-transitive.

A simple graph which is edge-transitive but  not  vertex-transitive is said to be  semisymmetric.  Such a graph is necessarily  bipartite.

 Come back later, we're
 still working on this one...

(2014-08-29)   Distance Transitivity
The  Desargues graph  is a cubic graph with 20 vertices and 30 edges.

I stumbled upon that graph in 1980,  as the smallest cubic graph of  girth  6.  It was first described by  Gérard Desargues (1591-1661).

 Come back later, we're
 still working on this one...

Levi graph  |  Pappus configuration  |  Pappus graph  |  Desargues configuration  |  Desargues graph

visits since March 19, 2007
 (c) Copyright 2000-2017, Gerard P. Michon, Ph.D.