Soit $\alpha\in\Bool$. 
On nomme $f^{\alpha}$ la fonction de $\Bool^{n-1}$ 
dans lui-même définie pour 
chaque $x\in\Bool^{n-1}$ par 
\[
f^{\alpha}(x)=(f_1(x,\alpha),\dots,f_{n-1}(x,\alpha)).
\]
On nomme $\Gamma(f)^\alpha$ le sous-graphe
de $\Gamma(f)$ engendré par le sous-ensemble
$\Bool^{n-1} \times \{\alpha\}$ de $\Bool^n$.

Énonçons et prouvons tout d'abord les lemmes techniques suivants:

\begin{Lemma}\label{lemma:subgraph}
$G(f^\alpha)$ est un sous-graphe de $G(f)$: chaque arc de $G(f^\alpha)$ est
un arc de $G(f)$. De plus si $G(f)$ n'a pas d'arc de $n$ vers un autre 
sommet $i\neq n$, alors on déduit
$G(f^\alpha)$ de $G(f)$ en supprimant le sommet $n$ ainsi que tous les 
arcs dont $n$ est soit l'extrémité, soit l'origine (et dans ce dernier  
cas, les arcs sont des boucles sur $n$).
\end{Lemma}

\begin{Proof}
Supposons que $G(f^{\alpha})$ possède un arc de  $j$ vers $i$ de signe 
$s$. Par définition, il existe un sommet $x\in\Bool^{n-1}$ tel que
$f'^{\alpha}_{ij}(x)=s$, et puisque 
$f'^{\alpha}_{ij}(x)=f'_{ij}(x,\alpha)$, on en déduit que $G(f)$ possède un arc
de $j$ à $i$ de signe $s$. Ceci prouve la première assertion. 
Pour démontrer la seconde, il suffit de  prouver que si
$G(f)$ a un arc de $j$ vers $i$ de signe $s$, avec $i,j\neq n$, alors
$G(f^\alpha)$ contient aussi cet arc. Ainsi, supposons que $G(f)$ a un 
arc de $j$ vers $i$ de signe $s$, avec $i,j\neq n$.
Alors, il existe
$x\in\Bool^{n-1}$ et $\beta\in\Bool$ tels que
$f'_{ij}(x,\beta)=s$. Si $f'_{ij}(x,\beta)\neq f'_{ij}(x,\alpha)$, alors
$f_i$ dépend du  $n^{\textrm{ème}}$ composant, ce qui est en contradiction 
avec les hypothèses.
Ainsi $f'_{ij}(x,\alpha)$ est égal à $s$.
On a donc aussi
$f'^{\alpha}_{ij}(x)=s$. Ainsi $G(f^\alpha)$ possède un arc de $j$ vers $i$ de signe $s$.
\end{Proof}

\begin{Lemma}\label{lemma:iso}
Les graphes $\Gamma(f^\alpha)$ et $\Gamma(f)^\alpha$ sont isomorphes.
\end{Lemma}

\begin{Proof}
Soit $h$ la bijection de $\Bool^{n-1}$ vers
$\Bool^{n-1}\times \{\alpha\}$ définie par $h(x)=(x,\alpha)$ pour chaque
$x\in\Bool^{n-1}$.
On voit facilement que $h$ permet de définir un isomorphisme
entre $\Gamma(f^\alpha)$ et $\Gamma(f)^\alpha$: 
$\Gamma(f^\alpha)$ possède un arc de $x$ vers $y$ si et seulement si 
$\Gamma(f)^\alpha$ a un  arc de $h(x)$ vers $h(y)$.
\end{Proof}


\begin{Proof}
{\sc{\hspace{-.76em}du théorème~\ref{th:Adrien} :}}
La preuve se fait par induction sur $n$. 
Soit $f$ une fonction de $\Bool^n$ dans lui-même et qui vérifie les hypothèses 
du théorème.
Si $n=1$ la démonstration est élémentaire:
en raison du troisième point du théorème, $G(f)$ a une boucle négative;
ainsi $f(x)=\overline{x}$ et $\Gamma(f)$ est un cycle de longueur 2.
On suppose donc que $n>1$ et que le théorème est valide pour toutes les 
fonctions de $\Bool^{n-1}$ dans lui-même. 
En raison du premier point du théorème, $G(f)$
contient au moins un sommet $i$ tel qu'il n'existe pas dans $G(f)$
d'arc de $i$ vers un autre sommet $j\neq i$.
Sans perte de généralité, on peut considérer que 
ce sommet est  $n$.
Alors, d'après le lemme~\ref{lemma:subgraph}, 
$f^0$ et $f^1$ vérifient les conditions de l'hypothèse.
Ainsi, par hypothèse d'induction $\Gamma(f^0)$ et
$\Gamma(f^1)$ sont fortement connexes. 
Et d'après le lemme~\ref{lemma:iso}, 
$\Gamma(f)^0$ et $\Gamma(f)^1$ sont fortement 
connexes. 
Pour prouver que $\Gamma(f)$ est fortement connexe, il suffit 
de prouver que $\Gamma(f)$ contient un arc $x\to y$ avec 
$x_n=0<y_n$ et un arc $x\to y$ avec $x_n=1>y_n$. 
En d'autres mots, il suffit de prouver que:
\begin{equation}\tag{$*$}
\forall \alpha\in\Bool,~\exists x\in\Bool^n,\qquad  x_n=\alpha\neq f_n(x).
\end{equation}

On suppose tout d'abord que $n$ a une boucle 
négative.
Alors, d'après la définition de 
$G(f)$, il existe $x\in\Bool^n$ tel que $f'_{nn}(x)<0$. 
Ainsi si $x_n=0$, on a  $f_n(x)>f_n(\overline{x}^n)$, et donc 
$x_n=0\neq f_n(x)$ et
$\overline{x}^n_n=1\neq f_n(\overline{x}^n)$; 
et si  $x_n=1$, on a 
$f_n(x)<f_n(\overline{x}^n)$, donc $x_n=1\neq f_n(x)$ et $\overline{x}^n_n=0\neq
f_n(\overline{x}^n)$. 
Dans les deux cas, la condition ($*$) est établie.

Supposons maintenant que  $n$ n'a pas de boucle négative.
D'après la seconde hypothèse, 
$n$ n'a pas de boucle, \emph{i.e.}, la valeur de $f_n(x)$
ne dépend pas de la valeur de $x_n$. 
D'après la troisième hypothèse, 
il existe $i\in \llbracket 1;n \rrbracket$ tel que $G(f)$ a un arc de 
$i$ vers $n$.
Ainsi, il existe $x \in \Bool^n$ tel que $f'_{ni}(x) \neq 0$ et donc 
%$n$ n'est donc pas de degré zéro dans $G(f)$, \emph{i.e.} 
$f_n$ n'est pas constante.
Ainsi, il existe $x,y\in \Bool^n$ tel que
$f_n(x)=1$ et $f_n(y)=0$. 
Soit  $x'=(x_1,\dots,x_{n-1},0)$ et
$y'=(y_1,\dots,y_{n-1},1)$. 
Puisque la valeur de $f_n(x)$
(resp. de $f_n(y)$) ne dépend pas de la  valeur de  $x_n$ (resp. de  $y_n$),
on a $f_n(x')=f_n(x)=1\neq x'_n$ (resp. $f_n(y')=f_n(y)=0\neq
y'_n$). 
Ainsi la  condition ($*$) est établie, et le théorème est prouvé.
\end{Proof}



%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "main"
%%% End: 
