Virittävät puut

Tehtäväsi on rakentaa suuntaamaton verkko, jolle voidaan muodostaa tasan $x$ erilaista virittävää puuta.

Verkossa tulee olla solmut $1,2,\dots,n$, ja verkon solmujen määrä $n$ saa olla enintään $40$. Verkossa ei saa olla kahta samanlaista kaarta, ja jokaisen kaaren tulee yhdistää kaksi eri solmua.

Toteuta tiedostoon spanning.py funktio create_edges, joka muodostaa halutunlaisen verkon. Funktion tulee palauttaa verkko listana kaaria. Verkon solmujen määrä $n$ on suurin kaaressa esiintyvä solmun numero.

Esimerkiksi lista [(1, 2), (2, 3), (1, 3)] tarkoittaa verkkoa, jossa $n=3$ ja jokaisen kahden solmun välillä on kaari. Tällä verkolla on kolme virittävää puuta, koska mikä tahansa kahden kaaren osajoukko on virittävä puu.

Voit muodostaa minkä tahansa verkon, jolla on halutut ominaisuudet. Funktiota testataan parametreilla $x=1,2,\dots,42$. Jos verkkoa ei voi muodostaa, funktion tulee palauttaa None.

def create_edges(x):
    # TODO

if __name__ == "__main__":
    print(create_edges(1)) # esim. [(1, 2), (2, 3)]
    print(create_edges(2)) # None
    print(create_edges(3)) # esim. [(1, 2), (1, 3), (2, 3)]