"Neha and me are walking together" should be also accepted, shouldn't it?
It shouldn't, actually. "Neha and me" wouldn't be correct English in this context. The sentence requires a subject ("I") rather than an object ("me"). You wouldn't say "Neha and me are walking" for the same reason you wouldn't say "Me am walking". Hope this helps.
In schoolbook English that's true but in spoken English "Neha and me" would be said. Remember, this is a Hindi lesson not a proper-English lesson.
The adverb together is not just साथ but साथ में in this exemple. Is there a rule?
I got this wrong because I left out the word "together".
My reasoning is:
Hindi takes four words to say "walking together".
Google translates साथ as "with" and में as "in".
That would be another preposition instead of the adverb, "together".
रहे (the continuous marker) looks like another clarifier that isn't always necessary (unless they mark you wrong without it).
साथ only really means "with" per se if it's के साथ. साथ gets used a few different ways, but together with में it is really one single adverb - and it's necessary. In English, "Neha and I are walking" doesn't necessarily mean we're walking together, just that we're both walking - and the same thing is true for Hindi if it were नेहा और मैं चल रहे हैं
Similarly, चल रहे हैं means something different then just चलते हैं would, again like in English. While some languages (like French or German) say "walk" and "be walking" the same, Hindi uses रहना to mean the progressive/continuous ("be walking"). So definitely both साथ (में) and चल रहे are necessary here for the intended meaning, and just translating it in English as "Neha and I walk" or "Neha and I are walking" wouldn't be accurate.