The minimum number of images for a walking cycle is 3. (left arm up, middle, right arm up).
Some old 2d games were even using only 2 (left arm up, right arm up). (In my game The Life Ruby my villagers have 2 frames but I use "middle" and only one image for "arm up". I feel its better when using only 2 images)
4 images appears odd to me.
5 images should make your character very smooth. (extreme left arm up, left arm up, middle/idle, right arm up, extreme right arm up)
At the end of the day its all about the style you want going on and how much time you wanna spend animating/drawing characters. Making the graphics is what takes the most time really. Think about it.