On this page
In 1959 Sharadchandra Shankar Shrikhande, working with his teacher R. C. Bose and with E. T. Parker, showed that a famous guess by Leonhard Euler about Latin squares was wrong. The same year he described a 16-vertex graph that breaks an easy assumption: that two networks with the same counts must be the same network. Here is how both work, with a pencil-and-paper check.
Who was S. S. Shrikhande?
Shrikhande was born in Sagar, in today's Madhya Pradesh, on 19 October 1917, the fifth of ten children of a father who worked at a flour mill (his Wikipedia biography). After a BSc in Nagpur, he earned his PhD in 1950 at the University of North Carolina at Chapel Hill under Bose. He later became the founding head of mathematics at the University of Mumbai, retiring in 1978. He died in Vijayawada on 21 April 2020, aged 102.
How did Shrikhande and Bose prove Euler wrong?
A Latin square of order n is an n × n grid of n symbols in which each symbol appears once in every row and once in every column. Two Latin squares are orthogonal when, laid on top of each other, every ordered pair of symbols appears exactly once.
Euler's puzzle of the 36 officers asked for an orthogonal pair of order 6. Failing to find one, he conjectured that none exists for any order of the form 4k + 2: 2, 6, 10, 14 and so on (mutually orthogonal Latin squares). In 1901 Gaston Tarry confirmed that order 6 is impossible (Scientific American), which made Euler look right.
In early 1959 Bose and Shrikhande built counterexamples of order 22, published in the Proceedings of the National Academy of Sciences. Parker then found one of order 10 with a one-hour computer search on a UNIVAC 1206 (mutually orthogonal Latin squares). Together they showed that orthogonal pairs exist for every order above 1 except 2 and 6, in a 1960 paper in the Canadian Journal of Mathematics, and earned the nickname “Euler's spoilers”. For the teacher's side, read R. C. Bose and the Latin squares that proved Euler wrong.
What is the Shrikhande graph?
A strongly regular graph srg(v, k, λ, μ) has v vertices, each with k neighbours, where every two adjacent vertices share λ common neighbours and every two non-adjacent vertices share μ (strongly regular graph).
The Shrikhande graph has 16 vertices, 48 edges and parameters (16, 6, 2, 2) (Shrikhande graph). To build it, label the vertices (a, b) with a and b from 0 to 3, and join two vertices when their difference, counted mod 4, is ±(1, 0), ±(0, 1) or ±(1, 1).
The 4 × 4 rook's graph, joining squares of a 4 × 4 board that share a row or column, has the same parameters. For every other board size, a strongly regular graph with the rook's parameters must be the rook's graph; n = 4 is the one exception, because of the Shrikhande graph (rook's graph). The difference is local: around each rook's-graph vertex the six neighbours form two separate triangles, while in the Shrikhande graph they form one hexagon.
Shrikhande's paper on this question, The Uniqueness of the L2 Association Scheme, appeared in a statistics journal, and the graph is used in statistical design (biography), the field of Ronald Fisher and why experiments randomise.
Can you check the Shrikhande graph by hand?
Yes, with the rule above and arithmetic mod 4 (so 0 − 1 = 3).
Neighbours of (0, 0): (1,0), (3,0), (0,1), (0,3), (1,1), (3,3). Six, so k = 6.
Adjacent vertex (1, 0) has neighbours (2,0), (0,0), (1,1), (1,3), (2,1), (0,3). Shared with (0, 0): (1,1) and (0,3), so λ = 2.
Non-adjacent vertex (2, 0) has neighbours (3,0), (1,0), (2,1), (2,3), (3,1), (1,3). Shared with (0, 0): (3,0) and (1,0), so μ = 2. Check the other eight non-neighbours yourself.
Test the identity (v − k − 1)μ = k(k − λ − 1) from the strongly regular graph definition: (16 − 6 − 1) × 2 = 18 and 6 × (6 − 2 − 1) = 18.
Join the adjacent pairs among the neighbours of (0, 0). You get one hexagon: (1, 0), (1, 1), (0, 1), (3, 0), (3, 3), (0, 3). On a rook's board you get two triangles.
The rule depends only on differences, so every vertex looks like (0, 0). If mod arithmetic or graphs are new to you, the Fermi Concept Library has a lesson for every concept in mathematics, each with its place in the map.
What can students learn from Shrikhande's work?
Small cases can mislead. Euler was right about order 6, which made his general guess feel safe.
Same numbers are not proof. Look for a property that tells two things apart.
When a counting argument goes wrong and you cannot see where, the Fermi Problem Library works through problems with a step-by-step solver that explains the reasoning rather than printing an answer. To see where graph theory began, read how Euler solved the Seven Bridges of Königsberg problem.
