def _graph_without_edge_labels(dg, vertices):
    """
    Expand the graph, by introducing new vertices in the middle of edges.
    Return the corresponding partition of the new vertices.

    There is one new vertex for each edge with label not equal to ``(1,-1)``.
    These vertices are numbered starting from the smallest available integer.

    Each edge having a non-trivial label is replaced by two consecutive edges,
    passing through one new vertex.

    EXAMPLES::

        sage: from sage.combinat.cluster_algebra_quiver.mutation_class import _graph_without_edge_labels
        sage: from sage.combinat.cluster_algebra_quiver.quiver import ClusterQuiver
        sage: dg = ClusterQuiver(['B',4]).digraph(); dg.edges()
        [(0, 1, (1, -1)), (2, 1, (1, -1)), (2, 3, (1, -2))]
        sage: _graph_without_edge_labels(dg, range(4)); dg.edges()
        ([[4]], ((1, -2),))
        [(0, 1, (1, -1)), (2, 1, (1, -1)), (2, 4, (1, -1)), (4, 3, (1, -1))]
    """
    vertices = list(vertices)
    edges = dg.edge_iterator(labels=True)
    edge_labels = tuple(sorted(set(label for _, _, label in edges
                            if label != (1, -1))))
    edge_partition = [[] for _ in edge_labels]
    i = 0
    while i in vertices:
        i += 1
    for u, v, label in dg.edge_iterator(labels=True):
        if label != (1, -1):
            index = edge_labels.index(label)
            edge_partition[index].append(i)
            dg._backend.add_edge(u, i, (1, -1), True)
            dg._backend.add_edge(i, v, (1, -1), True)
            dg._backend.del_edge(u, v, label, True)
            i += 1
            while i in vertices:
                i += 1
    return edge_partition, edge_labels