外部キーはmySQLのインデックスでなければなりませんか？

簡単な答え：はい、MySQLは外部キーのインデックス作成を強制します。

外部キーの詳細については、MySQLのドキュメントページを参照してください： http://dev.mysql.com/doc/refman/5.5/en/innodb-foreign-key-constraints.html