Everything is not well with dense graph backends

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

We discovered in #12318 that some functions of sage/geometry/polyhedra and sage/geometry/triangulation/point_configuration.py return wrong results if Graph(sparse = True) is replaced by Graph(sparse = False)

CC: @sagetrac-brunellus @rlmill

Component: graph theory

Issue created by migration from https://trac.sagemath.org/ticket/12387

[15606e31-f165-4fa5-94d5-bd9bfb0e1636]

comment:1

The dense graph code doesn't support edge labeling, but the code in point_configuration.py rely on this. Maybe it is a mistake that dense_graph doesn't crash and burn whenever someone call add_edge(u, v, nonNone) -- but it is consistent with cases like

sage: G=Graph(multiedges=False)
sage: G.add_edge(0,1)
sage: G.add_edge(0,1)
sage: G.edges()
[(0, 1, None)]

[vbraun]

comment:2

I wrote the code for polyhedra. It is definitely a bug if the graph silently gives the wrong answer just because some backend doesn't support edge labels.

[15606e31-f165-4fa5-94d5-bd9bfb0e1636]

comment:3

I started #12540 for this discussion.

I will investigate further if the lack of edge labels is the only source of the wrong results we spotted in #12318.