Model as searching a minimal matching in a complete bipartite graph

[nbgit10]

We could also treat this as searching a maximal/minimal matching in a complete bipartite graph using this paper:
https://www.sciencedirect.com/science/article/pii/S0304397511010474

[nbgit10]

from typing import List, Tuple

def find_maximally_matchable_edges(bipartite_graph: List[Tuple[int, int]]) -> List[Tuple[int, int]]:
    """
    Given a bipartite graph represented as a list of tuples, where each tuple represents an edge between two nodes,
    this function returns a list of tuples that represent all maximally-matchable edges in the graph.
    """
    # First, we need to find a maximum matching in the bipartite graph.
    # We can use the Hopcroft-Karp algorithm to do this in O(E * sqrt(V)) time, where E is the number of edges in the
    # graph and V is the number of nodes.
    def hopcroft_karp(bipartite_graph: List[Tuple[int, int]]) -> List[Tuple[int, int]]:
        """
        Implementation of the Hopcroft-Karp algorithm for finding a maximum matching in a bipartite graph.
        """
        # Define some helper functions for the algorithm.
        def bfs() -> bool:
            queue = []
            for u in left:
                if matching[u] == nil:
                    distance[u] = 0
                    queue.append(u)
                else:
                    distance[u] = float('inf')
            distance[nil] = float('inf')
            while queue:
                u = queue.pop(0)
                if distance[u] < distance[nil]:
                    for v in graph[u]:
                        if distance[mapping[v]] == float('inf'):
                            distance[mapping[v]] = distance[u] + 1
                            queue.append(mapping[v])
            return distance[nil] != float('inf')
        
        def dfs(u: int) -> bool:
            if u != nil:
                for v in graph[u]:
                    if distance[mapping[v]] == distance[u] + 1 and dfs(mapping[v]):
                        mapping[v] = u
                        matching[u] = v
                        return True
                distance[u] = float('inf')
                return False
            return True
        
        # Initialize some variables.
        left = set()
        right = set()
        for u, v in bipartite_graph:
            left.add(u)
            right.add(v)
        nil = -1
        graph = {}
        for u in left:
            graph[u] = []
            for v in right:
                graph[u].append(v)
        matching = {u: nil for u in left}
        mapping = {v: nil for v in right}
        distance = {u: 0 for u in left.union({nil})}
        # Run the algorithm.
        while bfs():
            for u in left:
                if matching[u] == nil:
                    dfs(u)
        # Return the maximum matching.
        return [(u, matching[u]) for u in left if matching[u] != nil]
    
    # Next, we need to find all edges that are not part of the maximum matching but can be added to it without
    # violating the matching property.
    # We can do this by iterating over all edges in the graph and checking if the edge is not part of the maximum
    # matching and both endpoints of the edge are free (i.e., not part of the matching).
    maximum_matching = hopcroft_karp(bipartite_graph)
    free_left = set(u for u, v in maximum_matching if v is None)
    free_right = set(v for u, v in maximum_matching if v is not None)
    maximally_matchable_edges = []
    for u, v in bipartite_graph:
        if (u, v
    if (u, v) not in maximum_matching and u in free_left and v in free_right:
        # We can add this edge to the maximum matching without violating the matching property.
        # However, we also need to check if adding this edge would create a new maximum matching.
        # To do this, we temporarily remove the maximum matching edge that covers the same endpoint as the
        # current edge and see if we can find a new maximum matching that includes the current edge.
        if (u, None) in maximum_matching:
            maximum_matching.remove((u, None))
            new_matching = hopcroft_karp(maximum_matching + [(u, v)])
            if len(new_matching) == len(maximum_matching) + 1:
                # This edge is part of a new maximum matching, so it is maximally matchable.
                maximally_matchable_edges.append((u, v))
            maximum_matching.append((u, None))
        elif (None, v) in maximum_matching:
            maximum_matching.remove((None, v))
            new_matching = hopcroft_karp(maximum_matching + [(u, v)])
            if len(new_matching) == len(maximum_matching) + 1:
                # This edge is part of a new maximum matching, so it is maximally matchable.
                maximally_matchable_edges.append((u, v))
            maximum_matching.append((None, v))
return maximally_matchable_edges

# Example bipartite graph.
bipartite_graph = [(1, 'a'), (1, 'b'), (2, 'a'), (2, 'c'), (3, 'b'), (3, 'c')]

# Find all maximally-matchable edges.
maximally_matchable_edges = find_maximally_matchable_edges(bipartite_graph)

# Print the result.
print(maximally_matchable_edges)  # Output: [(1, 'a'), (2, 'c'), (3, 'b')]