Why does my generate_semieuler function fail the edge-case tests for semi-Eulerian directed graphs?

Question

The task was: Write a function generate_semieuler that returns some directed semi-Eulerian graph on n vertices with m edges that has no bidirectional edges, or None if such a graph does not exist. Justify the correctness of the algorithm. You must use only networkX and built-in libraries. Problem Statement:

I need to write a function generate_semieuler that generates a directed graph with n vertices and m edges, which satisfies the following conditions: 1. The graph must be semi-Eulerian, i.e., it has an Eulerian path. 2. It must not contain bidirectional edges (no u -> v and v -> u ). 3. If no such graph exists, the function should return None. Template:

def generate_semieuler(n: int, m: int) -> nx.DiGraph | None:
    # your code goes here
    pass

Tests:

%%pytests

@pytest.mark.parametrize(
    "n, m",
    ((n, m) for n in range(0, 10) for m in range((n - 1) * (n - 2) // 2))
)
def test_generate_semieuler(n: int, m: int):
    graph = generate_semieuler(n, m)
    assert graph is not None
    assert graph.number_of_nodes() == n
    assert graph.size() == m
    graph.remove_nodes_from(list(nx.isolates(graph)))
    assert not graph or nx.has_eulerian_path(graph)

def test_generate_semieuler_edge_cases():
    check_semieulerian(7, 22)
    assert generate_semieuler(7, 23) is None
    check_semieulerian(6, 13)
    assert generate_semieuler(6, 14) is None

My code:

from itertools import permutations, combinations
import networkx as nx
from typing import Optional

def generate_semieuler(n: int, m: int) -> Optional[nx.DiGraph]:
    max_edges = n * (n - 1) // 2
    if m < 0 or m > max_edges:
        return None
    if n < 0:
        return None
    if n == 0:
        return nx.DiGraph() if m == 0 else None
    if n == 1:
        return nx.DiGraph() if m == 0 else None
    if m < 0 or m > n * (n - 1):
        return None

    G = nx.DiGraph()
    G.add_nodes_from(range(n))

    def can_add_cycle(H: nx.DiGraph, cycle_nodes):
        k = len(cycle_nodes)
        for i in range(k):
            u = cycle_nodes[i]
            v = cycle_nodes[(i + 1) % k]
            if H.has_edge(u, v) or H.has_edge(v, u):
                return False
        return True

    def add_cycle(H: nx.DiGraph, cycle_nodes):
        k = len(cycle_nodes)
        for i in range(k):
            u = cycle_nodes[i]
            v = cycle_nodes[(i + 1) % k]
            H.add_edge(u, v)

    def find_and_add_cycle(H: nx.DiGraph, length: int) -> bool:
        for cycle_nodes in combinations(range(n), length):
            for perm in permutations(cycle_nodes):
                if can_add_cycle(H, perm):
                    add_cycle(H, perm)
                    return True
        return False

    if m == 0:
        return G

    if 0 < m < n:
        # Создаём простой путь длиной m
        for i in range(m):
            G.add_edge(i, i + 1)
        return G

    if m == n - 1:
        # Путь через все n вершин
        for i in range(n - 1):
            G.add_edge(i, i + 1)
        return G

    if m == n:
        # Цикл из n рёбер
        for i in range(n):
            G.add_edge(i, (i + 1) % n)
        return G
    if m > n:
        # Основной n-цикл
        for i in range(n):
            G.add_edge(i, (i + 1) % n)
        L = m - n
        def add_single_edge(H: nx.DiGraph) -> bool:
            for u in range(n):
                for v in range(n):
                    if u != v and not H.has_edge(u, v) and not H.has_edge(v, u):
                        H.add_edge(u, v)
                        return True
            return False

        def add_two_edges_in_path(H: nx.DiGraph) -> bool:
            for a, b, c in permutations(range(n), 3):
                if (not H.has_edge(a, b) and not H.has_edge(b, a) and
                    not H.has_edge(b, c) and not H.has_edge(c, b)):
                    H.add_edge(a, b)
                    H.add_edge(b, c)
                    return True
            return False

        def add_extra_edges(H: nx.DiGraph, L: int) -> bool:
            if L == 0:
                return True
            mod = L % 3

            if mod == 0:
                count_3 = L // 3
                for _ in range(count_3):
                    if not find_and_add_cycle(H, 3):
                        # Если не получилось добавить трёхцикл, попробуем добавлять одиночные рёбра
                        for __ in range(3):
                            if not add_single_edge(H):
                                return False
                        # Проверим, что всё ещё корректно
                        if H.size() > m:
                            return False
                return True

            elif mod == 1:
                if L >= 4:
                    # Пытаемся добавить один четырёхцикл
                    if not find_and_add_cycle(H, 4):
                        # Если не удалось, попробуем другой подход:
                        # Добавим одиночное ребро, уменьшим L на 1 (теперь L делится на 3).
                        if not add_single_edge(H):
                            return False
                        L -= 1
                        return add_extra_edges(H, L)
                    L -= 4
                    count_3 = L // 3
                    for _ in range(count_3):
                        if not find_and_add_cycle(H, 3):
                            # Попытка заменить трёхцикл несколькими ребрами, если не получается
                            for __ in range(3):
                                if not add_single_edge(H):
                                    return False
                            if H.size() > m:
                                return False
                    return True
                else:
                    # L=1: добавляем одиночное ребро
                    return add_single_edge(H)

            else:  # mod == 2
                if L >= 4:
                    # Добавляем один четырёхцикл
                    if not find_and_add_cycle(H, 4):
                        # Попытка замены на одиночные ребра, если 4-цикл не удался
                        for __ in range(4):
                            if not add_single_edge(H):
                                return False
                        L -= 4
                        return add_extra_edges(H, L)
                    L -= 4
                    return add_extra_edges(H, L)
                else:
                    # L=2: пытаемся добавить два ребра в путь
                    if not add_two_edges_in_path(H):
                        # Если не получилось, добавляем по одному ребру
                        if not add_single_edge(H):
                            return False
                        if not add_single_edge(H):
                            return False
                    return True
            
        if not add_extra_edges(G, L):
            return None

        # Дозаполняем до m рёбер, если чего-то не хватает
        while G.size() < m:
            if not add_single_edge(G):
                return None
        return G

    return None


def check_semieulerian(n: int, m: int):
    max_edges = n * (n - 1)
    if m < 0 or m > max_edges:
        return None
    graph = generate_semieuler(n, m)
    assert graph is not None, f"Граф не должен быть None для n={n}, m={m}"
    assert graph.number_of_nodes() == n, f"Граф должен содержать {n} вершины, а содержит {graph.number_of_nodes()}"
    assert graph.size() == m, f"Граф должен содержать {m} рёбер, а содержит {graph.size()}"

    graph_filtered = graph.copy()
    graph_filtered.remove_nodes_from(list(nx.isolates(graph_filtered)))
    assert nx.has_eulerian_path(graph_filtered), f"Граф для n={n}, m={m} должен иметь эйлеров путь"

    for u, v in graph.edges():
        assert not graph.has_edge(v, u), f"В графе не должно быть двунаправленных рёбер между {u} и {v}"

I don't understand how I can rewrite the code to check the condition for the existence of an Euler path (0 or 2 vertices with odd degrees as far as I remember) I tried balancing the degrees of vertices with additional edges. I modified helper functions to prioritize balancing degrees, but this broke the edge constraints. All tests are passed except the last part of testing-code.