def METHOD_NAME(
    two_qubit_gate_prob: float,
    connectivity_graph: nx.Graph,
    random_state: random.RandomState,
) -> nx.Graph:
    """
    Args:
        two_qubit_gate_prob: Probability of an edge being chosen
            from the set of candidate edges.
        connectivity_graph: The connectivity graph for the backend
            on which the circuit will be run.
        random_state: Random state to select edges (uniformly at random).
    Returns:
        Returns a set of edges for which two qubit gates are to be
        applied given a two qubit gate density and the connectivity graph
        that must be satisfied.
    """
    connectivity_graph = connectivity_graph.copy()
    candidate_edges = nx.Graph()
    final_edges = nx.Graph()
    final_edges.add_nodes_from(connectivity_graph)
    while connectivity_graph.edges:
        num = random_state.randint(connectivity_graph.size())
        edges = list(connectivity_graph.edges)
        curr_edge = edges[num]
        candidate_edges.add_edge(*curr_edge)
        connectivity_graph.remove_nodes_from(curr_edge)
    for edge in candidate_edges.edges:
        if random_state.uniform(0.0, 1.0) < two_qubit_gate_prob:
            final_edges.add_edge(*edge)
    return final_edges