[BUG] `isgraphical` returns true for a non-graphical sequence

[dave-ck]

Description of bug, expected and actual behavior isgraphical returns true for a non-graphical sequence, namely [4,2,2,2,0]. It should return false on this input.

How to reproduce Call the function isgraphical on input [4,2,2,2,0].

Code demonstrating bug

using Graphs

println(isgraphical([4,2,2,2])) # should print false, prints false
println(isgraphical([4,2,2,2,0])) # should print false, prints true
println(isgraphical([4,2,2,2,0]) == isgraphical([4,2,2,2])) # should definitely print true, prints false

Version information

Julia Version 1.10.4
Commit 48d4fd4843 (2024-06-04 10:41 UTC)
Build Info:
  Official https://julialang.org/ release
Platform Info:
  OS: Windows (x86_64-w64-mingw32)
  CPU: 16 × AMD Ryzen 7 5800H with Radeon Graphics
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-15.0.7 (ORCJIT, znver3)
Threads: 1 default, 0 interactive, 1 GC (on 16 virtual cores)   
Environment:
  JULIA_EDITOR = code
  JULIA_NUM_THREADS =

Output of ]status Graphs is [86223c79] Graphs v1.9.0.

Additional context I at first thought the implementation allowed self-loops, in which case the sequence can be realized by (for example) the graph on vertices a,b,c,d,e with edges a-a, a-b, b-c, a-c, a-d, d-d. However, [4,2,2,2] returns false (as it should if we disallow self-loops). The implementation should be consistent (optionally with a flag to allow or disallow self-loops, if this is a needed feature).

If the bug is limited to cases where there is a vertex of degree zero, an easy fix would be to add the line

degs = [deg for deg in degs if deg > 0]

at the beginning of the function (e.g. after checking the sum of degrees is even, and before the sequence length is computed).

[dave-ck]

Quick note: isdigraphical([4,2,2,2,0],[4,2,2,2,0]) correctly returns false. In general, (if the digraphical function is correctly implemented - I only checked that sequence), a fix can be to simply assign: isgraphical(seq) = isdigraphical(seq, seq).

[gdalle]

Thanks for reporting this, and sorry for the lack of reactivity in this part of the ecosystem!

I'm not familiar with this function, but from what I read on the Wikipedia page of the Erdos-Gallai theorem (referenced in the docstring), that theorem only applies to simple graphs. This means self-loops should be disallowed. On the other hand, degrees equal to zero appear to be supported.

Can you spot something wrong in the implementation? If so, a fix would be welcome and easy to review I think: https://github.com/JuliaGraphs/Graphs.jl/blob/34fd1dc35b518e277c09efe86c2281825e5bc4ef/src/connectivity.jl#L796-L822

[simonschoelly]

It would be very nice if we had a flag to allow or disallows self-loops. A while ago I tried to come up with a variant of the Erdős–Gallai for self-loops but I did not succeed so far. And I also could not find anything in the literature.

Until we do so we should explicitly state in the documentation that this does not work for self-loops.

[simonschoelly]

This paper might have some solution. One difference there is that for Graphs.jl we only add 1 to the degree of a vertex if it has a self-loop. But that paper (and I think in general the literature might do that) adds 2 to the degree.

[simonschoelly]

So for a quick solution we should state in the documentation that self-loops and multiple edges are not allowed.

[simonschoelly]

See also #303