1
$\begingroup$

While reading a paper on unicyclic unbalanced signed graphs, I met the following fact:

The determinant of the incidence matrix of a unicyclic unbalanced graph (i.e. the cycle of the graph has an odd number of negative edges) is $\pm 2$.

For the proof of the fact, the author has referred to a well-known paper of Zaslavsky's ("Signed graphs"), which is very complicated.

Does anybody know any source for a simpler proof?

$\endgroup$

1 Answer 1

1
$\begingroup$

Strict answer. Strictly construed, I think that the answer is no, there isn't any other published simpler proof. (I know a thing or two about this topic.)

Generalized answer. However, the most important thing to point out, hopefully helpful (since being told that something is easy is often helpful) to the opening poster:

this fact is trivial to prove.

('Trivial' in the second sense of trivial, i.e., not requiring any advanced knowledge, only knowledge taught in the usual 'trivium' of mathematics; in this case: the easy definitions, Laplace expansion of determinants, and induction.)

I could make this thread into a "source for a simpler proof", but currently have no time to do so. For the time being, it is hopefully helpful to the opening poster to

  • again assure the opening poster that this is easy to prove

  • assure the opening poster that this is not in any way deeply 'rooted' in Zaslavsky's 1983 paper, rather, a proof can easily be read-off from Zaslavsky's paper (briefly: do the obvious reduction, via Laplace-expansion, to the special instance where the unicyclic graph is itself a circuit, and prove, by induction, a dedicated little lemma for this instance; this is all you need).

  • again, it would be easy to give an exposition here, but I don't know whether I will ever get round to do so (since I wouldn't work with Zaslavky's notation outright (though there isn't anything 'wrong' with it), and I would feel it necessary to put this little fact into context (by contrasting it with the 'usual' lemma of Poincaré that any incidence matrix of an oriented abstract finite simplicial complex is totally unimodular, which to a very casual reader might look like an contradiction (which of course it is not).

  • Include the most relevant part of

Thomas Zaslavsky: Signed Graphs. Discrete Applied Mathematics 4 (1987). 47-74

which is

enter image description here

(source: op. cit. pp. 68-69; colors added)

Please, do not wait for a complete exposition (from me).

So, briefly, I think Zaslavsky's 1983 paper will be enough for you. You can start with the proof of Lemma 8A.2 and work backwards in the paper, and this algorithm should stop rather soon.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.