(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.
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).
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.)
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.
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 simpleundirected 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
(those two nodes are called adjacent whenever
aij is nonzero, especially
in the case of undirected graphs).
The adjacency matrix of a simple digraph
has Boolean elements (either 0 or 1).
Normally, the adjacency matrix of a digraph is a square matrix
of nonnegative integers.
However, we may also usefully consider rectangularmatrices
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:
å kaikbkj
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.
(2023-09-30) Incidence Matrix
of a graph with n nodes and m edges.
M is a rectangular matrix with n rows and m columns.
When all is said and done, the incidence matrix M can be construed
as a square-root of the Laplacian matrix.
(2010-10-24) The Three-Utilities Problem
Providing 3 cottages with 3 utilities without crossing lines.
A 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).
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.
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:
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 matrixA of the digraph G is:
1
0
1
1
1
0
1
0
0
1
1
1
1
0
0
1
0
1
1
1
1
0
0
1
1
0
1
1
1
0
1
0
0
0
1
1
1
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
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:
A2
3
2
5
5
5
1
3
2
2
3
5
5
5
1
2
3
2
3
5
5
5
1
2
3
3
2
5
5
5
1
3
2
1
1
3
3
3
0
1
1
5
5
8
8
8
3
5
5
5
5
8
8
8
3
5
5
5
5
8
8
8
3
5
5
A3
14
13
26
26
26
6
14
13
13
14
26
26
26
6
13
14
13
14
26
26
26
6
13
14
14
13
26
26
26
6
14
13
6
6
13
13
13
2
6
6
26
26
47
47
47
13
26
26
26
26
47
47
47
13
26
26
26
26
47
47
47
13
26
26
A4
73
72
138
138
138
33
73
72
72
73
138
138
138
33
72
73
72
73
138
138
138
33
72
73
73
72
138
138
138
33
73
72
33
33
65
65
65
14
33
33
138
138
258
258
258
65
138
138
138
138
258
258
258
65
138
138
138
138
258
258
258
65
138
138
30
156
826
Now, the characteristic polynomial of the matrix A is:
det ( xI - A ) =
x 4 ( 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 theorem,
A 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) :
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).
(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.
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).
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").
1
0
1
1
1
0
1
0
0
1
1
1
1
0
0
1
0
1
1
1
1
0
0
1
1
0
1
1
1
0
1
0
0
0
1
1
1
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
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) :
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
4
6
8
10
12
14
16
18
Single
30
156
826
4406
23562
126104
675074
3614142
Double
158
828
4408
23564
126106
675076
3614144
(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).
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).
With 6 nodes, Hamiltonian cubic graphs have
729 possible markings (36 ).
Two configurations lead to different numbers of
satisfactory markings (156 or 158).
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.)
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.
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 ).
Non-isomorphic graphs with the same tally
exist, since the 80 Hamiltonian 12-node cubic graphs
yield only 75 tallies:
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:
30
158
828
842
2n = 4
2n = 6
2n = 8
23564
24470
2n = 12
2n = 20
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.
A symmetric graph is both vertex-transitive
and edge-transitive.
A graph automorphism of a simple
graph G is a bijectionf 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.
(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).
The Desargues graph is pne of only 12 finite trivalent distance-transitive graphs.
(Biggs and Smith, 1971).
The product of two graphs, as defined bellow, is also known under many
names (which may denote different things outside of the context of graph theory):
conjunction,
direct product,
cardinal product,
relational product,
Kronecker product,
weak direct product,
categorial product...
The product of two graphs G and H is the graph whose set of nodes is
the cartesian product
V(G) × V(H) of their respective sets of nodes,
endowed with the set of edges which makes two such compound vertices
adjacent just when both of their components are,
in G and H respectively. Formally:
V( G × H ) = V(G) × V(H)
E( G × H ) = { ( (g,g') , (h,h') ) |
(g,g') Î E(G) &
(h,h') Î E(H) }
(2019-12-23) Coloring the Tensor-Product or Two Graphs
A counterexample to Hedetniemi's conjecture (1966) was found in 2019.
A famous conjecture put forth in 1966, by Stephen Hedetniemi
was that the chromatic number of the tensor product
of two graphs was the lesser of their two chromatic numbers.
Yaroslav Shitov disproved that in 2019.
(2020-12-02) Promiscuity among heterosexuals.
Heterosexual females are just as promiscuous as heterosexual males.
Almost all studies of this topic ignore this simple mathematical remark (which can be made rigorous,
as shown below).
At best, their experimental results are compatible with it:
"Self-reported sexual encounters are relatively similar between the sexes."
(MS
thesis, p.19) Lilly Pamela Harvey
(Lincoln, 2015).
Most of the time however, nonsensical "results" are reported which
simply demonstrate that data wasn't properly collected
(if anonymity isn't properly secured, men over-report and women under-report).
Univ Chicago, The Social Organization
of Sexuality, 1994: Men have 74% more
women partners than women have men.
NBC News, American Sex Survey, 2004: Men have 233% more women partners.
U.S. National Center for Health Statistics
study, 2007: Men have 175% more women partners.
This is a remark pertaining to a finite bipartite
graph whose N nodes are humans
(either male or female) whith E edges corresponding to heterosexual relationships
between a male and a female (i.e., at least one intercourse between them).
The heterosexual promiscuity
of a human is the degree of the corresponding node.
For a rigorous result to be obtained,
we must consider the entire human population.
There are two ways to do so:
All the humans who ever lived. This is slightly problematic if we aim for
a rigorous equality, because of the ambiguity which must have existed at the
time when the ancestors of modern humans could no longer interbreed with other apes
(the latter term being also ill-defined around the time when those could no longer
interbreed with other mammals, and so forth).
All humans alive today.
Retaining the latter definition,
every newborn has zero promiscuity and so does anyone who has survived all his or her partners!
That's not what most people have in mind when they talk about promiscuity, but that's
a good enough approximation when discussing a youngish age bracket.
People who have few dead ex-lovers. Or none.
It's probably better to use the former definition to derive the main conclusion.
Once it's so established that the promiscuities of men and women are exactly
the same when age considerations are somehow discarded,
then it's clear that it's clear that this remain approximately so when they're not.
Any report of a big difference is pure fiction.
Proof
As is often the case, the proof of the theorem is trivial once we agree
on definitions. Let's call x and y the number of females and males respectively
(x+y=N). The average heterosexual promiscuity of females is p=E/x
and that of males is q=E/y. If x=y, then p=q.