Matematické Fórum

Andrejka3

Ahoj,
Příklad zní.
Je-li graf $G=(V,E)$ hranově tranzitiví a zároveň není vrcholově tranzitivní, pak je bipartitní.
Dokaž.

Umím to dokázat pro případ, kdy graf nemá vrchol stupně nula.
Můj důkaz:
Je $|V| \geq 2$ , jinak by byl graf triviálně vrcholově tranzitivní.
Volme $e \in E, \; e=\{u,v\}$ . To udělat mohu, protože kdyby $E = \emptyset$ , pak by všechny vrcholy měly nulový stupeň a navíc by byl graf vrcholově tranzitivní.
Označme:
$V_u:=\{w \in V ; \; \exists e' \in E \exists \varphi \text{ automorfismus takový, že }\varphi(e)=e', \varphi(u)=w\}$ ,
$V_v:=\{w \in V ; \; \exists e' \in E \exists \varphi \text{ automorfismus takový, že }\varphi(e)=e', \varphi(v)=w\}$ ,
kde $\varphi(e)=\{\varphi(u),\varphi(v)\}$ .
Chci ukázat, že tyto (neprázdné) množiny jsou disjunktním rozkladem $V$ :
Graf je vrcholově tranzitivní, proto je $V_u \cup V_v=V$ .
Kdyby $V_u \cap V_v \neq \emptyset$ , pak volím $z \in V_u \cap V_v$ .
Chci ukázat, že tento předpoklad vede ke sporu s tím, že $G$ není vrcholově tranzitivní.
Pro libovolné dva vrcholy $x,y \in V$ platí - jsou buďto oba v jedné z dvou množin $V_u,V_v$ , pak ale existuje automorfismus, který zobrazuje BÚNO $\varphi_1: u \mapsto x$ a jiný, $\varphi_2:u \mapsto y$ . Pak $\varphi_2 \circ \varphi_1^{-1}: x \mapsto y$ a je to automorfismus.
Pokud jsou naopak oba vrcholy v jiné z dvou množin, je BÚNO
$\varphi_1: u \mapsto x$ , $\varphi_2: v \mapsto y$ , ale mame $\varphi_3: u \mapsto z$ a $\varphi_4: v \mapsto z$ , odkud $\varphi_2 \circ \varphi_4^{-1} \circ \varphi_3 \circ \varphi_1^{-1}$ je automorfismus $G$ , který zobrazuje $x$ na $y$ .
$G$ je vrcholově tranzitivní, což je spor s předpokladem, že není. Musí tedy být $V_u \cap V_v = \emptyset$ , a je tedy $G$ bipartitní.

Jak to mám udělat, pokud existuje vrchol nenulového stupně? Nebo pak tvrzení neplatí?
Díky,
A.

PS: definice: $G=(V,E)$ graf

Autor skryl část textu. Zobrazit/skrýt!

Andrejka3

Myslím, že mám protipříklad:
Graf s vrcholy $\{1,2,3,4\}$ , kde vrcholy 1,2,3 tvoří kružnici a vrchol 4 má nulový stupeň. Takový graf je hranově tranzitivní, není vrcholově tranzitivní a není bipartitní.

Matematické Fórum

#1 24. 07. 2012 22:25 — Editoval Andrejka3 (25. 07. 2012 08:46)

Graf, hranově tranz. + není vrcholově tranz., pak bipartitní

#2 25. 07. 2012 08:35 — Editoval Andrejka3 (25. 07. 2012 08:43)

Re: Graf, hranově tranz. + není vrcholově tranz., pak bipartitní

Zápatí