Does there exist a nonsingular graph for which the determinant of its adjacency matrix remains the same upon deleting a vertex?

Question

Consider simple graphs. Any simple graph $G$ is called nonsingular if its $(0,1)$-adjacency matrix $A(G)$ has nonzero determinant. Does there exist any nonsingular simple graph whose determinant value remains the same upon deleting a vertex?

Answer 1

Proposition. The unique smallest graph w.r.t. number of edges of the requested kind is

. (This graph is isomorphic to graph no. 126 below).

It has $6$ vertices and $8$ edges. The determinant of its adjacency matrix is equal to $-4$. Deleting the unique degree-two vertex with two degree-three neighbors (lowermost in picture) leaves a graph whose adjacency matrix has determinant $-4$, too.

Among the 156 isomorphism types of $6$-vertex graphs, the only other graph of the kind requested by the OP is the graph found by Philipp Lampe at 2018-03-05 18:38:11Z, that is,

,

(this graph is isomorphic to graph no. 116 below)

and there does not exist any example on five vertices or less.

The above graph has $6$ vertices and $12$ edges. Hence the answer at 2018-03-05 18:38:11Z provided an example of the requested kind with smallest possible number of vertices but missed the example of smallest number of edges (by four edges). ${}\hspace{125pt}$ End of Proposition.

On the content of this answer.

Content. This answer contains

1. a proof of the Proposition (assuming that Sage tells the truth),

2. a correction of two errors in a table in the following published article (which is very relevant to the OP's question):

[A2012] Alireza Abdollahi, Determinants of adjacency matrices of graphs, Transactions on Combinatorics, Vol. 1, No. 4 (2012), pp. 9-16

Notation. For brevity, throughout, 'a.d. (of a graph $G$)' is shorthand for the much longer phrase 'determinant of the adjacency matrix (of a graph $G$)'. (The abbreviation 'a.d.' is for 'adjacency determinant'.)

On the illustrations. Each of the screenshots of the Sage-output below is given in sufficient resolution to make all numbers visible (perhaps you'll have to zoom or click on the picture).

I doctored the pictures of the output in various ways to make them more useful (in particular, the a.d.-value is highlighted in blue), but only to the extent that this was doable in a bearable amount of time. In particular, I did not in any way try to improve upon Sage's graph-drawing. I do not understand the rationale behind the order in which the graphs are listed by Sage, and did not change that either. Not interfering with this ordering makes the data more reproducible. The blue numbers, which I added, give the order in which the graphs were spewn out by Sage.

Details.

I start with item 2. above, because it is useful to have that table available for later double-checking.

On item 2. The incorrect table is this:

(source: [A2012; p. 11]; annotations added; the cyan box around the url is in the original)

The rows marked as wrong are certainly wrong, no matter whether Sage is correct or not. I checked this carefully, and will give reasons below (in short, the rows marked red can be seen to be wrong from the exponents/multiplicities alone, disregarding the values).

The rows marked 'checked with Sage' are probably correct, since I could reproduce each of them with the following Sage code^(*):

g=graphs(9) v=list(g)

len(v)

results=[]

for i in range(274668):

$\hspace{10pt}$ results.append(v[i].adjacency_matrix().det())

from collections import defaultdict

histo = defaultdict(int)

for k in results:

$\hspace{10pt}$ histo[k] += 1

histo

(here 'histo' is for 'histogram'^(**)) whereupon the following output is produced:

defaultdict(, {0: 133174, -128: 2, 2: 6767, 4: 6950, 6: 4669, 8: 1566, 10: 1349, 12: 1156, 14: 695, 16: 606, 18: 106, 20: 297, 22: 173, 24: 240, 26: 95, 28: 91, 30: 61, 32: 46, 34: 5, 36: 32, 38: 28, 40: 3, 64: 1, 42: 17, 44: 16, 54: 3, -72: 12, 60: 3, -64: 7, -96: 3, -60: 5, -56: 17, -54: 12, -50: 27, -48: 13, -46: 20, -44: 39, -42: 47, -40: 103, -38: 52, -36: 110, -34: 128, -32: 593, -30: 199, -28: 295, -26: 392, -24: 765, -22: 579, -20: 869, -18: 2747, -16: 2247, -14: 1805, -12: 3062, -10: 4290, -8: 17582, -6: 8531, -4: 14901, -2: 57065})

I have annotated the table in various ways; in particular, I have shifted the entries in the row for $n=6$ a little to the left to make room for what I consider to be the correct values. (Incidentally, the only error in [A2012] for this row is the multiplicity of the a.d.-value $4$; the rest of that row is correct. The multiplicity of $4$ is $5$, not $2$ as given in the table.)

How to prove that the rows for $n=5$ and $n=6$ are wrong? This already follows by summing the exponents. Needless to say, for each row, the sum of the exponents must be equal to the number of isomorphism classes (aka number of unlabelled graphs) of graphs with that number of vertices. According to both A000088 and a table on page 105 of [Flajolet-Sedgewick, Analytic Combinatorics, CUP, version 26 June 2009],

• on $3$ vertices, there are $4$ isomorphism classes of graphs,
• on $4$ vertices, there are $11$ isomorphism classes of graphs,
• on $5$ vertices, there are $34$ isomorphism classes of graphs,
• on $6$ vertices, there are $156$ isomorphism classes of graphs,
• on $7$ vertices, there are $1044$ isomorphism classes of graphs,
• on $8$ vertices, there are $12346$ isomorphism classes of graphs,
• on $9$ vertices, there are $274668$ isomorphism classes of graphs,

while

• in the row for $n=3$, the sum of multiplicities is $3+1=4,$

  which is consistent,

• in the row for $n=4$, the sum of multiplicities is $1+7+3=11,$

  which is consistent,

• in the row for $n=5$, the sum of multiplicities is $1+25+6+1=33,$

  which contradicts the number $34$ above,

• in the row for $n=6$, the sum of multiplicities is $3+5+32+99+10+2+2=153,$

  which contradicts the number $156$ above,

• in the row for $n=7$, the sum of multiplicities is $2+2+13+21+20+690+204+40+17+25+5+5 = 1044,$

  which is consistent,

• in the row for $n=8$, the sum of multiplicities is $2+2+5+5+7+21+51+43+90+79+128+251+581+813+6551+2416+758+240+73+139+24+23+32+8+1+3=12346,$

  which is consistent,

• in the row for $n=9$, the sum of multiplicities is $2+3+12+7+5+17+12+27+13+20+39+47+103+52+110+128+593+199+295+392+765+579+869+2747+2247+1805+3062+4290+17582+8531+14901+57065+133174+6767+6950+4669+1566+1349+1156+695+606+106+297+173+240+95+91+61+46+5+32+28+3+17+16+3+3+1=274668,$

  which is consistent.

Furthermore,

On item 1. To prove the Proposition, we first note that it is obvious that there does not exist an example on three vertices or less.

Now we show that there is no example on four vertices. For this, we first note that the only graphs on three vertices without isolated vertices (and hence having any chance of resulting in a nonzero a.d.) are

• the path, with three vertices with a.d. $0$, and

• the triangle, with a.d. $2$.

Hence the only candidates of graphs on four vertices of the kind requested by the OP are those whose a.d. is $2$. Now, the Sage code

for G in graphs(4):

$\hspace{10pt}$ print([G.adjacency_matrix(),G.adjacency_matrix().det(),G.show()])

produced the following output:

and this shows that there isn't any four-vertex graph with a.d. $2$. (This is also corroborated by the row for $n=4$ in the table in [A2012; p. 11].) This completes the proof that there is no example on four vertices.

We now show that there is no example on five vertices. Both from the Sage-output above, and from the table in [A2012] we see that the only nonzero a.d.-values on four vertices are $1$ and $-3$. Therefore, the only candidates for an example on five vertices are those graphs on five vertices with an a.d. of either $1$ or $-3$. Now, the Sage code

for G in graphs(5):

$\hspace{10pt}$ print([G.adjacency_matrix(),G.adjacency_matrix().det(),G.show()])

produced the following output:

Both the above, and the table in [A2012; p. 11], strongly suggest that there does not exist any graph on five vertices with a.d. equal to $-3$ or $1$. If this is true (which seems very likely in view of [A2012] reporting to have used $\textsf{GAP}$, a different software from Sage), then this implies that there indeed does not exist an example on five vertices. Needless to say, this is not a mathematical proof; sadly, I cannot imagine how a proof could be given which is better than inspection of all instances, even when using a well-know 'combinatorical' formula for the interpretation determinants found in [H1962; p. 208].That formula still involves both positive and negative summands, which is why I do not think it merits to be considered a genuinely combinatorial interpretation (this is more of an aesthetic judgement, of course). Harary's interpretation so far does not seem to help with the open problem, and it does not offer any computational advantages.

We now prove that on six vertices there are exactly two examples of the kind requested by the OP. From the 34 graphs shown above, it follows that very probably the only nonzero a.d.-values on five vertices are $-4$, $-2$, $2$, $4$. So, the only candidates for examples of the kind requested on six vertices are those with these a.d.-values. Now, the Sage code

for G in graphs(6):

$\hspace{10pt}$ print([G.adjacency_matrix(),G.adjacency_matrix().det(),G.show()])

produced the following output. The same remarks as above apply with regards to the presentation. In particular, my not improving the graph-drawing is more obvious here, since, in several cases such as graphs no. 114, and 184 (and most especially no. 105 and 114, which has some almost invisible edges), Sage's artistic 'choices' were not so sage after all. Most of the time though, Sage did remarkably well in drawing the graphs, and in all cases all information is clear, since I give the adjacency matrices alongside the graphs. I feel that I should justify my not discarding the graphs with an isolated vertex (and hence obviously a vanishing determinant). I did not discard them because this makes the answer more systematic, reproducible and checkable.

The above strongly suggests that there does not exist a graph on six vertices with a.d.-value $-2$ or $2$. There do exist ten graphs with a.d.-value $-4$ or $4$ though, namely, graphs no. 63, 65, 109, 110, 113, 116, 121, 126, 127, 149. We have to consider each of these in turn, and analyze whether there are vertices whose deletion leaves a graph with the same a.d.-value.

For the graph no. 63, which has a.d. $4$, the deletion of any vertex results in a graph isomorphic to graph no. 30 (in the list of graphs with five vertices), which has a.d. $-2\neq 4$, so 63 is not an example.

For the graph no. 65, which has a.d. $4$, we have to distinguish cases for analyzing the effects of the vertex-deletions.

• when deleting vertex $4$, a graph isomorphic to graph no. 34 results, which has a.d. $-4\neq 4$.

• when deleting vertex $0$ or $1$, a graph isomorphic to graph no. 31 results, which has a.d. $-2\neq 4$.

• when deleting vertex $2$, a graph isomorphic to graph no. 30 results, which has a.d. $-2\neq 4$.

• when deleting vertex $3$ or $5$, a graph isomorphic to no. 32 results, which has a.d. $-2\neq 4$.

Since the above exhausts all possible vertex-deletions, and the a.d. always changed, the graph no. 65 is not an example.

For the graph no. 109, which has a.d. $-4$, the deletion of any vertex results in a graph isomorphic to no. 16. which has a.d. $0\neq -4$, hence no. 109 is not an example.

For the graph no. 110, which has a.d. $-4$, we again have to distinguish cases: deleting vertex $0$ results in a graph isomorphic to graph no. 22, which has a.d. $2\neq -4$, while deleting vertex $1$ or $2$ results in graph no. 16 with a.d. $0$, and deleting $3$ or $4$ results in no. 31 with a.d. $-2\neq -4$, and finally deleting vertex $5$ results in no. 17 with a.d. $0\neq -4$; this shows that graph no. 110 is not an example either.

For the graph no. 113, which has a.d. $-4$, deleting $0$ results in graph no. $22$ with a.d. $2\neq -4$, while deleting $1$ or $2$ results in no. 23 with a.d. $0\neq-4$, while deleting $3$ or $4$ results in no. 32 with a.d. $-2\neq-4$, and finally deleting $5$ results in no. 24. This shows that no. 113 is not an example.

For the graph no. 116, which has a.d. $4$, deleting any of $0$, $1$, or $2$ results in no. 26 with a.d. $-2\neq 4$, while deleting $3$ or $4$ results in no. 33 with a.d. $-2\neq 4$, but deleting $5$ results in no. 29 with a.d. $4=4$. Hence no. 116 is an example, namely the example found by Philipp Lampe. In this example, exactly one of the vertices has the required property.

For the graph no. 121, which has a.d. $4$, deleting vertex $0$ or $2$ results in no. 24 with a.d. $-2$, while deleting $1$ results in no. 34 with ad. $-4\neq 4$, while deleting $3$ results in no. 31 with a.d. $-2\neq 4$, while deleting $4$ results in no. 33 with a.d. $-2\neq 4$, and deleting $5$ results in no. 26 with a.d. $-2\neq 4$. This shows that graph no. 121 is not an example.

For the graph no. 126, which has a.d. $-4$, deleting $0$ or $4$ results in no. 23 with a.d. $0$, while deleting $1$ results in no. 16 with a.d. $0\neq -4$, while deleting $2$ or $5$ results in no. 17 with a.d. $0\neq -4$, but deleting $3$ results in no. 34 with a.d. $-4=-4$. Therefore, graph no. 126 is another example of the required kind. This is the example given at the very beginning of this answer.

For the graph no. 127, which has a.d. $-4$, deleting $0$, $3$ or $4$ results in no. 24 with a.d. $-2\neq-4$, while deleting $1$, $2$ or $5$ results in no. 17 with a.d. $0\neq -4$. This exhausts all vertices and shows that no. 17 is not an example.

For the graph no. 149, which has a.d. $4$, and deleting $0$ or $5$ results in no. 26 with a.d. $-2\neq4$, while deleting $1$, $2$, $3$ or $4$ results in no. 32 with a.d. $-2\neq 4$. This shows that no. 149 is not an example.

We have now considered all the candidates, and found exactly two examples of the kind requested by the OP, namely, the two graphs given in the proposition at the beginning of this answer. This proves the proposition.

Concluding remarks.

• The rather small ratio of $\frac{2}{156} = \frac{1}{78}$ suggests the question of whether the limit

$\lim_{n\to\infty}\frac{\text{number of unlabelled graphs on $n$ with at least one vertex of the required kind}}{\text{number of all unlabelled graphs on $n$}}$

exists and what it is. Everything other than its being $0$ would seem surprising to me, but I don't know how to prove this.

• Embarassingly, I don't know a construction which would answer the obvious question of

whether for every $n\geq 6$ there exists at least one graph on $n$ with the required property (i.e., non-zero determinant of the adjacency matrix, and there is at least one vertex whose deletion leaves a graph with the same determinant of adjacency matrix).

• Noam Elkies at 2018-03-05 17:23:37Z pointed out the interesting ambiguity in the verbal phrasing of the OP's question, which leaves it unclear what the intended logical quantifier governing the deleted vertex is. Both interpretations are possible. While the OP's accepting the answer at 2018-03-05 18:38:11Z seems to suggest that the OP meant an existential quantifier, the other interpretation is interesting and an open question; i.e.,

Open problem. Does there exist a finite graph such that the determinant of its adjacency matrix is nonzero and deleting any of its vertices results in a graph whose adjacency matrix has the same value as before?

Update 13 March, 2018. I am now inclined to think that, contrary to my initial expectations, a graph of the above kind is impossible: In two idle hours I experimentally checked almost all the named graphs at

http://doc.sagemath.org/html/en/reference/graphs/sage/graphs/graph_generators.html

and in the case of the graph-constructor allowing parameters, I experimented with many value of these parameters. Moreover, I tested many thousands of circulant graphs (by now, roughly $10^6$ nonisomorphic circulants, on between 11 and 100 vertices, roughly speaking), and for many sizes of 'connection sets', with each 'connection sets' randomly chosen. I also tested random graphs (though there one knows from the get-go that there is no chance, because the vertex-deleted a.d. clearly won't all have the same value). The results was this:

There are more examples that I care to describe of the a.d. being non-zero while the a.d. after vertex-deletion differs from the previous a.d. by $1$ only. However, amazingly, not a single example of the kind required by the OP was found among thousands of non-isomorphic graphs. This surprised me, because it was contrary to what I had expected. From my experiences with smallish circulants (which came 'close' to what the OP and Noam Elkies asked for), I had expected that randomly mining slightly larger circulants would quickly turn up an example. This was not the case, and I went to circulants on about a hundred vertices, and to intersection sets of size about $5$ (resulting in $10$-regular graphs).

I am well-aware that circulants are very special graphs and that generalizing from them to all graphs is rather unwarranted. By now, I would be very surprised though, if an affirmative answer of the question in the open problem existed which was a circulant. There seems to be some principle at work which prevents the difference

$\det(\mathrm{A}(G))-\det(\mathrm{A}(G)|_{(n\setminus\{i\})\times(n\setminus\{i\})})$

which for a circulant of course does not depend on $i\in n$, down to $0$, except in the trivial case in which the determinants are both $0$. To repeat myself, this difference can easily brought to $1$ or $-1$ (I have seen hundreds of examples), though I still do not know how to characterize the circulants achieving that.

There might be an appreciable mathematical truth behind these experimental results. Perhaps there is even an understandable reason. I in particular find it intriguing that one can get to within $1$ of what is requested, which is as close as it can get except for an outright solution.

So, unless you cherish the process itself, don't search around in http://doc.sagemath.org/html/en/reference/graphs/sage/graphs/graph_generators.html for an example, for I predict that you won't find any. (This is a rough intuitive judgement of the probability, 'Bayesian' as it were, not an exact frequentist statement.) In my personal opinion it seems more advisable to try to prove the conjecture that such a graph is impossible.

Update March 14, 2018. I think it is not unlikely that someone (like me) finds the article

[BLP2014] Bapat, R.B.; Lal, A.K.; Pati, S. A formula for all minors of the adjacency matrix and an application. Spec. Matrices 2, No. 1, 89-98 (2014).

and (like me) initially thinks that this might help with the open problem. I cannot find anything wrong with this interesting article, but I think it might save someone else time to point out that contrary to what the title might suggest, the article [BLP2014] can be completely ignored as far as the open problem is concerned; the reason is that the main focus of [BLP2014] are minors which are indexed by such sets such that the set indexing the 'rows' of the minor is disjoint from the set indexing the 'columns' of the minor, whereas the OP's problem involves minors indexed by sets of the form $(n\setminus\{i\})\times(n\setminus\{i\})$ with $i\in n$, which is about as far from the main purview of [BLP2014] as possible. I am not saying that [BLP2014] had a misleading title: indeed, every kind of minor is taken care of, but for minors of the kind relevant to the present open problem, the formula in [BLP2014] reverts to precisely the formula in [H1962, page 208] (to see this, one has to read until Remark 3.2 in [BLP2014]).

References.

[A2012] Alireza Abdollahi, Determinants of adjacency matrices of graphs, Transactions on Combinatorics, Vol. 1, No. 4 (2012), pp. 9-16

[B1993] Norman Biggs, Algebraic Graph Theory, Cambridge University Press, 1993, ISBN 9780521458979

[BLP2014] Bapat, R.B.; Lal, A.K.; Pati, S. A formula for all minors of the adjacency matrix and an application. Spec. Matrices 2, No. 1, 89-98 (2014)

[H1962] Frank Harary, The Determinant of the Adjacency Matrix of a Graph, SIAM Review, Vol. 4, No. 3. (1962), pp. 202-210.

Footnotes.

^(*) Incidentally, the case $n=10$ seems to be within the reach of contemporary machines, even with the non-optimized, high-level code I gave above. Yet it is within the reach of the machines available to me. If some readers happens to have both access to a powerful machine/cluster, and has and Sage installed, then running the code I gave with

'graphs(9)' replaced with 'graphs(10)',

and

'range(274668)' replaced with 'range(12005168)' (which is the number of isomorphism classes of graphs on 10 vertices)

will probably yield the a.d.-values for $n=10$ in a reasonable amount of time and memory.

I would appreciate being sent the output of 'histo' for $n=10$ (e.g. as a comment), and would then add it to this thread. The case $n=11$ is, I guess, out of reach without renting a sizeable amount of time and memory on a supercomputer.

^(**) It is worth pointing out that the distribution of a.d.-values is not symmetric around $0$. This might seem surprising at first thought, but becomes less surprising if one realizes that the usual operations which swap the sign of a determinant, and which often can be used to prove symmetry of vanishing expected values, are not available here: swapping two rows (or columns) does not result in another adjacency-matrix of a graph.

Answer 2

There exists a simple graph $G=(V,E)$ together with a vertex $v\in V$ such that $\operatorname{det}(A(G))$ and $\operatorname{det}\left(A(G\backslash\{v\})\right)$ are equal and non-zero.

Example. The determinant of the adjacency matrix of the complete graph $K_n$ is known to be $(-1)^{n-1}(n-1)$. Let $G'=K_5$ be the complete graph on the vertex set $[1,5]$. By the previous remark $\operatorname{det}(A(G'))=4$. Suppose that $G$ is obtained from $G'$ by adding a vertex $0$ and two edges $(0,1)$ and $(0,2)$.

Let $E_{0,0}$ be the $6\times 6$ matrix indexed by $[0,5]\times [0,5]$ with entry $1$ at $(0,0)$ and zeros otherwise. Then the matrix

\begin{align*} A(G)-E_{0,0}=\left(\begin{matrix} -1&1&1&0&0&0\\ 1&0&1&1&1&1\\ 1&1&0&1&1&1\\ 0&1&1&0&1&1\\ 0&1&1&1&0&1\\ 0&1&1&1&1&0 \end{matrix}\right) \end{align*}

is singular because $(2,1,1,-1,-1,-1)^T$ is an eigenvector with eigenvalue $0$. Hence \begin{align*} 0=\operatorname{det}(A(G)-E_{0,0})=\operatorname{det}(A(G))-\operatorname{det}(A(G')), \end{align*} so that $\operatorname{det}(A(G))=\operatorname{det}(A(G'))=4$.