graphs: StaticSparseBackend (i.e., immutable graphs) sorts the vertices by default

[cyrilbouvier]

Steps To Reproduce

sage: G = Graph([['b', 'a'], []])
sage: list(G)
['b', 'a']
sage: Gim = Graph([['b', 'a'], []], immutable=True)
sage: list(Gim)
['a', 'b']

Expected Behavior

The vertex of Gim should not be sorted by default.

Actual Behavior

The vertex of Gim are sorted by default.

Additional Information

The sorting happens in src/sage/graphs/base/static_sparse_backend.pyx (line 515).
It should not be the default behaviour as it breaks most complexity claims around graphs.

I try removing the sort in PR #38427 but I gave up as it breaks too many doctests in very different parts of SageMath (Lie algebra, elliptic curve, categories, poset, ...).

Even the code of StaticSparseBackend (the class implementing immutable graphs) rely on the fact that the vertices are sorted as illustrated by the fact that the two methods iterator_edges and iterator_unsorted_edges are the same.

This issue may be linked to the meta issue #35902

Environment

• OS: debian 11
• Sage Version: 10.4

Checklist

• I have searched the existing issues for a bug report that matches the one I want to file, without success.
• I have read the documentation and troubleshoot guide