Valaki segít gráf rajzolásba?

2. miatt nem lehet egy csúcs fokszáma sem 2.

2. feltétel a leggazdaságosabban akkor teljesül, ha minden fokszám 3.

Jó lenne egy kocka élhálózata, de abban nincs háromszög, ezért 3. nem teljesül.

Akkor vegyünk egy szabályos nyolcszöget a csúcsokkal és a 8 oldalával együtt. Vegyünk hozzá egy leghosszabb átlót és a rá szimmetrikus 3 átlót. Ez jó lesz, van háromszög is benne.

Szerintem nem lehet a kiírásnak megfelelőt csinálni, mert bármely 3 él eldobásával nem esik két komponensre a gráf. (Van olyan 3 él, amitől szétesik, de nem bármelyik 3 esetén.)

Ettől az utolsó feltételtől eltekintve jó, amit Vurugya Béla írt. Szóval minden csúcsnak 3 éle kell legyen, ami összesen 8·3/2 = 12 él. Ennél kevesebbel nem oldható meg. A kocka élhálója tényleg nem jó, de átrendezhető:

[link]

Az AB élet töröljük, helyette behozzuk az AC élet, hogy legyen háromszög. De ekkor B-nek túl kevés, a C-nek túl sok fokszáma lesz, amit korrigálhatunk, ha a DC él helyett a DB élet vesszük be.

Az így keletkező gráf ekvivalens azzal, amit a nyolcszögből kiindulva javasolt Vurugya Béla, ez látszik az ábrán. Ugyancsak egyenértékű velük mondjak az is, ami az ábrán a harmadik gráf.