Megoldás: 5.32
Tegyük fel, hogy a
KG(n,k) gráf komplementere éltranzitív. Az az
5.30. feladat szerint vagy nem összefüggő, vagy az átmérője 1 vagy 2 lehet. Nyilvánvaló, hogy 1 csak úgy lehet, ha
k=1.
Másrészt a
K.II.5.21. feladat szerint csak akkor nem összefüggő, ha
n≤2k. Ha
n<2k, akkor a gráf üres, ennek komplementere éltranzitív. Ha
n=2k, akkor a gráf egy teljes párosítás, s ennek komplementere szintén éltranzitív.
Marad az az eset, ha
k 1 és
n 2k. Ebben az esetben a gráf összefüggő, de nem a teljes gráf, tehát ha éltranzitív, akkor átmérője 2. Ez viszont azt jelenti, hogy bármely két nem-diszjunkt
k elemű részhalmazhoz kell lennie egy olyan
k elemű részhalmaznak, ami mindkettőtől diszjunkt. Vagyis ennek igaznak kell lennie akkor is, ha a két nem-diszjunkt részhalmaznak csak egy közös pontja van. Ekkor uniójuk
2k-1 elemű, tehát ebben az esetben
n≥3k-1.
Másrészt az is világos, hogy ha a komplementer éltranzitív, akkor bármely két nem-diszjunkt,
k elemű részhalmazhoz pontosan ugyanannyi, mindkettőtől diszjunkt,
k elemű részhalmaznak kell lennie. Világos, hogy az olyan
k elemű részhalmazok diszjunktak mindkét részhalmaztól, amelyek az uniójuk komplementerében vannak. Ha azonban
k≥3, akkor nyilván van két olyan nem-diszjunkt,
k elemű részhalmaz, amelyek uniója
2k-1 elemű és olyan is, amelyek uniója
2k-2 elemű, s ezeknek a komplementerében nem lehet ugyanannyi
k elemű részhalmaz.
Tehát az
n≥3k-1 esetben csak a
k=2 eset jön szóba. Az
5.31. feladatban láttuk, hogy ebben az esetben a Kneser-gráf komplementere valóban éltranzitív.
Összesítve azt kaptuk, hogy a
KG(n,k) Kneser-gráf komplementere a
k=1,
k=2 esetekben éltranzitív, valamint az
n≤2k esetben. A
k=1 esetben teljes gráfról van szó, az
n≤2k-1 esetben üres gráfról, az
n=2k esetben független élekről (közelebbről teljes párosításról). Az egyetlen ,,igazán érdekes" eset a
k=2 eset, amikor a Kneser-gráf átmérője 2. A legkisebb ilyen ,,érdekes" eset épp a Petersen-gráf.