[ENIGME] remplir une GRILLE

Considérons le graphe d'une grille carrée, de taille n*n.
Par exemple, pour n=5 :
http://sketchtoy.com/70760924
Si on prend deux sommets quelconques, il existe bien sûr plusieurs chemins différents permettant de lier l'un à l'autre.
Voici par exemple 3 chemins différents permettant de relier les 2 points verts :
http://sketchtoy.com/70760927
Le chemin rose est très long, en revanche le chemin vert et le chemin orange sont tous deux des "plus courts chemins" : je ne peux pas relier les deux points verts en passant par moins de 4 arêtes.

Enigme :

a) Est-il possible de trouver n "plus courts chemins" qui sont tous disjoints les uns des autres (ie ils ne doivent pas passer par les même sommets) et qui couvrent tous les sommets de la grille ?
Réponse :Evidemment que oui... voici deux exemples pour la grille 5x5, qui se généralisent évidemment. Il existe bien sûr plein d'autres exemples.
http://sketchtoy.com/70760930
http://sketchtoy.com/70760929

b) Quel est le nombre minimal de "plus courts chemins" disjoints deux à deux dont on a besoin, pour recouvrir une grille de taille n x n ?
Réponse :Jsp. pour n=1, n=2 ou n=3 on prouve facilement qu'on ne peut pas faire mieux que n chemins. Pour le cas général, c'est moins clair, mais j'imagine que c'est pareil.

Le 13 juin 2022 à 23:24:37 :
Non Kévin on fera pas ton devoir maison de théorie des graphes

Je me doute que tu n'es pas capable de le faire tkt.
C'est pas un DM, c'est une "énigme" qu'on m'a posé mais le type qui me l'a posée n'a pas non plus la solution.
Je cherche dans mon coin et je ne lirai pas le détail des différentes réponses tant que j'aurai pas abandonné, mais au cas où j'abandonne j'aimerais bien que quelqu'un ait trouvé une solution élégante.