Dimostrazione Teoria dei grafi

[Mega-X]

Premetto che a disegnare sono una schiappa (e peggio ancora lo sono a disegnare al computer) e quindi scusate per la bassa qualità dell'immagine.. (fatta con mspaint per giunta.. )


Dimostrare che dato un grafo planare e con i suoi $n$ nodi tutti di grado 2 (come quello di figura), se si definisce un operatore che dato un certo senso fa coincidere ad un nodo il suo successivo, dimostrare che se questa operazione viene ripetuta $n-1$ volte è la stessa cosa di effettuare tale operazione $1$ volta nel senso opposto

Propongo anche il caso generalizzato a $k$ volte, cioè a dire se si effettua l'operazione in un senso $k$ volte allora sarà la stessa cosa effettuare la stessa operazione $n-k$ volte dall'altro senso..

[vl4dster]

io direi che deve essere cosi' per complementarita': $n = k+(n-k)$ dunque e' chiaro che se fai $k$ passi
in un senso te ne mancano $n-k$ per tornare dov'eri. Ovviamente per il verso opposto il discorso e' simmetrico
e dunque se supponi per assurdo di essere in due vertici distinti dopo $k$ passi in un verso e dopo $n-k$ nell'altro
ottieni un assurdo.
per complicare piu' del necessario direi una cosa del genere:
siano $1,...,n$ i vertici di $G$.
sia $1$ il vertice da cui partiamo a valutare i due operatori $f':V->V$, $f'':V->V$.
Chiaramente possiamo chiamare i vertici come ci pare, dunque
consideriamo una ri-enumerazione dei vertici seguendo l'ordine di $f'$, ovvero in modo che $f$ mandi un vertice nel suo successore:
per $a>=0$, $f'^{(a)}(1) = (a" mod"(n))+1$
per $b>=0$, $f''^{(b)}(1) = ((-b)" mod"(n))+1$
Allora $f'^{(k)} = (k" mod"(n))+1$
$f''^{(n-k)}(1) = ((k-n) " mod(n)")+1 = (k" mod"(n))+1 = f'^{(k)} $

[Mega-X]

beh in effetti il teorema è di facile dimostrazione..