The usual definition of the word 'sentence' demands that there be a verb*, so the question becomes nonsensical.
However, rephrasing to 'Don't use structures other than sentences,' we must say that this is a very shaky rule-of-thumb rather than a grammatical requirement. In conversation, sentence fragments / sentence substitutes such as Tomorrow, Yes, If you must, On the table are often given as answers and are quite acceptable. Follow-on fragments are also quite acceptable in informal writing: She is 70 years old. Perhaps older.
Look up articles on 'sentence fragments' and 'crots' on the internet for guidance on actually using these structures. Overuse is not advisable, and only normal patterns should be used:
Where is the paper?
Where will you go to?
- Uncle Bob's farm.
- To Uncle Bob's farm.
What are you writing about?
- The Civil War.
- ??About the Civil War.
*The fact that 'sentence fragments' are sometimes called 'minor sentences' is, I feel, confusing.