(2009-07-16) The puzzle that begat graph theory. Solved by Euler in 1735.
Themartyred town ofKönigsbergwas renamed Kaliningrad in 1946, in honor ofMikhail Ivanovich Kalinin(1875-1946). The town and its surroundings had been attributed to the USSR at thePostdam Conferencein 1945, as the Allies split that part of Europe among themselves. Kaliningrad is nowin a Russian enclave between Poland and Lithuania. It is home to about 430,000 people.
WhenLeonhard Euler(1707-1783) visited the town,there were seven bridges over the Pregel riverin 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 pathwhich 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 thingand presented his formal result to the membersof the SaintPetersburg Academy on August 26, 1735.
In the process, Euler founded graph theory andestablished its earliest nontrivial result in the form of a simple necessaryand sufficient condition for the existence of the type of path theinhabitants 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 hisoriginaldrawings 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 givenbelow which views an undirected graph as a special case of a directed graph, uniquely specifiedby its adjacency matrix. The elementary concept introduced by Euler in 1735corresponds only to symmetricalmatriceswhose 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 theirextremities (for directed graphs, we woulddistinguish the origin and the destination of each edge and tally theformer total as the outdegree of a given nodeand 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 evendegree. (: As we walk through an Eulerian circuit, we arrive at a given nodeas 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 (: Those two nodesmust 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 makesthe 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 alonga 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 allpossible) you must use what's known as Fleury's algorithm(1883) : Always move along an edge whose removal from the setof unvisited edges will leave that set connected.
More precisely, it's the edges which must all be connectedtogether; an Eulerian or semi-Eulerian graph may include any number ofirrelevant 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 toprove 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 fairlystraightforward, it seems that no such proof appeared in printbefore the posthumous publication (in 1873) of the argument devised byCarl Hierholzer (1840-1871)shortly before his death.
(2009-01-14) A special type of directed graphs.
An undirected graph is just a directed graph (or digraph) whoseadjacency matrixA is symmetrical.
In the (unusual) generalization of digraphs which featuresadjacency matrices whose elements arecomplex 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 isHermitian).
(2008-06-26) 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).
A digraph, simple or not, is fully specified byits so-called adjacency matrix whose element a is equal to the number of edgesgoing from node i to node j (those two nodes are called adjacent whenever a is nonzero, especiallyin the case of undirected graphs). The adjacency matrix of a simple digraphhas Boolean elements (either 0 or 1).
Normally, the adjacency matrix of a digraph is a square matrixof 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 fromdisjointsets.
Incidentally, abipartite graph is also a special type of undirected graph whosenodes can be divided into two disjoint sets U and V such thatevery [undirected] edge of the graph connects one node of U to one node of V. Either viewpoint defines in terms of graphs a structure isomorphicto the relations between U and V (fundamentally, a relation is asubset of the Cartesian productUV).
The digraph (or the bipartite graph) whose adjacency matrix is the product of two adjacency matricesturns is simply the digraph in which tere are asmany edges from node i to node j as there are ways to go from i to jusing 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 andbkj ways to go from k to j, thenthe number of ways to go from i to j via all possible nodesk is given by the following formula, which is alsohow the relevant element in the product of the adjacency matrices iscomputed:
kaikbkj
Applying this remark iteratively, we see that the matrix An is the adjacency matrix of a digraphwhich has as many edges from i to j as there are paths fromi to j consisting of n edges of the graph whose adjacency matrixis A.
This result was put to good use by Max Alekseyev in the solution, presentedbelow,of an enumeration problem originally posed by Philip Brocoum.
(2023-09-30) M is a rectangular matrix with n rows and m columns.
When all is said and done, the incidence matrix M can be construedas a square-root of the Laplacian matrix.
(2023-09-30)
(2023-09-30) for simple graphs The determinant of anyfirst minor of the Laplacian matrixis the number spanning trees.
A tree is a connected graph containing no cycles.
In an undirected graph, the Laplacian matrix ... ...
(2010-10-24) 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 surfaceof a sphere) without crossing the lines associated tograph edges (those lines connect the points associated tothe graph vertices).
(devised byKazimierzKuratowski (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 haveat least 4 edges (since a triangular facewould necessarily include a line connecting either two cottages or twoutility providers, which is disallowed). As each edge belongs to exactly two faces, this would imply the existence ofat 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 acomplete outlineof the following solution to theproblem originally posed by Philip Brocoum,whereby it is asked in how many different ways 2n people in a circle can avoid eye contactif they must look left, right, or directly across the circle. (The names "screaming circles" and/or "silent circles" come fromthe fact that this activity has actually been practicedwith the dramatic rule that two people who make eye contact mustboth scream.)
There are 8 possible ways that two diametrically opposed people may gaze withoutlooking 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 thecounterclockwise direction,then eye contact occurs neither between the respective "top" membersof 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 otherby 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 goingfrom one node to its flipped counterpart. The number of all such silent circles is thus the sum of all highlighted elements in then-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 ( xIA ) = 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 theCayley-Hamilton theorem, A is a root of the above polynomial. Thus, the successive matrix elements at a given locationin the n-th powers of A obey the following linear recurrence (for n>3). So does any sum of such elements.
an+4 = 8an+3 16an+2 + 10an+1an
In particular, the sum of the elements of An for the locations highlighted above obey this recurrence and the sequenceis fully defined by stating that it starts with 2, 6, 30 and 156 (corresponding respectively to n = 0, 1, 2, 3).
The cases n = 0 and n = 1 are part of a valid basis for the solution sequencebut are not relevant to Brocoum's original problem, which arguably starts witha 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 choseto put this sequence on record (asA141221) with a dubious start at n = 1 with value 0 (to include the degenerate case of a "circle" of 2 people who have no choicebut to look at each other).
(2008-06-28) A screaming game for short-sighted people.
Beforegeneralizing Brocoum's poser,let's present another version of thescreaming game which can be analyzedwith the same tools.
Consider a "prism" of 2n people: They are arranged in two concentriccircles 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 neighborson the same circle.
The problem of enumerating the number of ways 2n people can avoid eye contactunder such rules can be dealt with exactly as above, with the samedigraph G, except that the nodes of G bear different labels,using the following 8 symbols associated with each pairof partners. The top of the symbol indicates what direction the partnerin the inner circle is looking at (right = counterclockwise) whereas the bottom of the symbol tells aboutthe parner in the outer circle. (A vertical arrow thusindicates that one partner is looking at the other. No symbols havetwo 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 labelsif we assume that each circle contains at least 3 people (that's a more severe restriction than for the previous analysis, which remainedperfectly valid even for n = 2). This yields the following adjacency matrix, where diagonal elementsare now "highlighted" to indicate that a silentsolution 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 metbefore. So, Alekseyev's recurrence holds between its successive powers (at least beyond the fourth power) and, therefore, between the sumsof the highlighted elements,which are now actuallythe 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 = 7an+2 9an+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 withthe numbers 158, 828 and 4408, which appear in that capacitywithin the more general discussion of thefollowing section.
Note, in particular, that 4 people can be arranged in a proper screamingcircle (the corresponding graph is a tetrahedron, for which 30 of the81 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 gamewith adouble circle (the above "prism" type) than in an ordinary game where "partners"are opposite each other in asingle 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) 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 degreesof 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 twospouses are neighbors, with the rule that one personmay 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 toundirectedcubic Hamiltonian graphs (namely, graphs where 3 edges meet at each node and whichallow a circuit that goes through every node once and only once).
With 4 nodes, there's only one such graph (the regular tetrahedron) in which there are30 different satisfactory markings (out of 81 unrestricted possibilities).
With 6 nodes, Hamiltonian cubic graphs have729 possible markings (36). Two configurations lead to different numbers ofsatisfactory 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-graphallowing 900 markings.)
Note that the leftmost of the above graphs is isomorphic to the Brocoumcase (where two spouses are always in diametrically opposed positions). To prove this, you may want to look for aHamiltoniancircuit 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 and4602.
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 nodeswhich are not Hamiltonian (namely, the Petersen graphand the bridged graph ).
Non-isomorphic graphs with the same tallyexist, since the 80 Hamiltonian 12-node cubic graphsyield only 75 tallies:
The numbers of cubic graphs with 2n nodesis 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).
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 graphswith 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) 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 andwhose edges connect all pairs of E which have one common extremity in G.
(2008-07-14) A symmetric graph is both vertex-transitive and edge-transitive.
A graph automorphism of a simple graph G is abijectionf of its vertices such thatthe 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) 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).
(2019-12-23)
The product of two graphs, as defined bellow, is also known under manynames (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 isthe cartesian product V(G) × V(H) of their respective sets of nodes, endowed with the set of edges which makes two such compound verticesadjacent 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) Least number of colors needed to color all adjacent nodes differently.
(2019-12-23) 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 productof two graphs was the lesser of their two chromatic numbers. Yaroslav Shitov disproved that in 2019.
(2020-06-12) Nodes are neurons. Edges are synapses.
(2020-12-02) 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."(MSthesis, p.19) Lilly Pamela Harvey (Lincoln, 2015).
Most of the time however, nonsensical "results" are reported whichsimply 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 relationshipsbetween 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 fora rigorous equality, because of the ambiguity which must have existed at thetime 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 longerinterbreed 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'sa 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 exactlythe 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 agreeon 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.
(2008-06-28) 
).
Non-isomorphic graphs with the same tallyexist, since the 80 Hamiltonian 12-node cubic graphsyield only 75 tallies:
