Ash-Shama'il Al-Muhammadiyah, Book 11, Hadith 81 (In-Book)

Abu Hurayrah reports: Rasulullah Sayyidina Rasulullah sallallahu alaihe wasallam said: One should not wear one shoe and walk. Both shoes should be worn or both shoes should be removed.

حَدَّثَنَا إِسْحَاقُ بْنُ مُوسَى الأَنْصَارِيُّ، قَالَ‏:‏ حَدَّثَنَا مَعْنٌ، قَالَ‏:‏ حَدَّثَنَا مَالِكٌ، عَنْ أَبِي الزِّنَادِ، عَنِ الأَعْرَجِ، عَنْ أَبِي هُرَيْرَةَ، أَنَّ رَسُولَ اللهِ صلى الله عليه وسلم، قَالَ‏:‏ لا يَمْشِيَنَّ أَحَدُكُمْ فِي نَعْلٍ وَاحِدَةٍ، لِيُنْعِلْهُمَا جَمِيعًا، أَوْ لِيُحْفِهِمَا جَمِيعًا‏.‏

also referenced under: Book 10, Hadith 77 (English)