def METHOD_NAME(
    connectivity_graph: nx.Graph,
    random_state: random.RandomState,
    two_qubit_gate: cirq.Gate = cirq.CNOT,
) -> cirq.Circuit:
    """
    Args:
        connectivity_graph: A graph with the edges for which the
            two-qubit Clifford gate is to be applied.
        random_state: Random state to choose Cliffords (uniformly at random).
        two_qubit_gate: Two-qubit gate to use.
    Returns:
        A circuit with a two-qubit Clifford gate applied to each edge in
        edges, and a random single-qubit Clifford gate applied to every
        other qubit.
    """
    gates = [
        two_qubit_gate.on(cirq.LineQubit(a), cirq.LineQubit(b))
        for a, b in list(connectivity_graph.edges)
    ]
    qubits = nx.Graph()
    qubits.add_nodes_from(nx.isolates(connectivity_graph))
    gates.extend(
        list(random_single_cliffords(qubits, random_state).all_operations())
    )
    return cirq.Circuit(gates)