Actually, that should be "Don't use sentence fragments!" so as not to break its own rule. What is a sentence fragment? Anything that looks like a sentence — starts with a capital letter and ends with a period — but is not a syntactically complete standard sentence.
This "rule" has some validity as a general guideline, especially to help adolescents get over some of their more atrocious writing habits. But respected authors and well-educated writers have always used exceptions to the "rule" for good effect. Here are some examples:
Sentences without verbs
It's obvious that a sentence needs a verb. Right? If not, why not?
Did you see what I just did there? I didn't need to say "Is that right? If it is not, why is it not?" You can sometimes get by without restating things. This is called ellipsis, and is found in many a well-polished work of prose. No need for extra information. The shorter the better. Out with the longwinded and in with the concise.
Oh, yes, and then there are incomplete sentences like those last three.
In "The shorter the better," the the is actually a holdover from an old adverbial form meaning "in that" or "by that" that we also see in "none the less" and "so much the better." Sentences of this type are presenting the existence of a condition, and any verb used would be an empty placeholder just to fill a syntactic role. You can use a verb, but you don't always have to.
Similar to those are sentences that present the presence or absence of a thing: "No need for extra information." Again, the filler "There is" can sometimes simply be left unsaid, if you're aiming for a brisker tone.
Sentences such as "Out with the old, in with the new" and "Up yours" are just slightly different. They also use adverbs, but they're imperatives, not simple statements. In these, a verb is unnecessary (you could say it's implied) because the movement or change of state is expressed with the adverbial use of the preposition — yes, you can have an imperative without a verb. And while "Up yours" is (ahem) very informal, "Out with the old and in with the new" is something even a prim grammarian might say.
Do respected authors do these things? They certainly do. An elliptical response such as "With pleasure" is so standard that it has been used by Charles Dickens, Nathaniel Hawthorne, Henry James, E.M. Forster, and who knows how many others. It should go without saying that respected authors from before Shakespeare to the very present have also used "Why?" and "How so?" and similar elliptical response questions to very good effect.
For adverbials, Shakespeare gives us some good examples, including two famous lines from Macbeth: "Out, damned spot! out, I say!" and "Out, out, brief candle!" For dropping the empty "There is," no need to look farther than the respected economist John Stuart Mill: "No need of any other faculty than the ape-like one of imitation."
This doesn't exhaust the set of acceptable sentences without verbs, either. There are also expressions that have a performative effect, such as "Welcome" and "Good evening." Who would insist that a person always say "I bid you welcome" or "I wish you a good evening?"
And now for sentences that begin with conjunctions
There is another kind of "sentence fragment" that may actually have a subject and a verb and, as needed, an object — but it starts with a conjunction (and, but, because, if, etc.) or relative pronoun (which, who) that attaches to something in a previous sentence. The idea that this is wrong is a grammatical superstition confected in the 18th century and foisted on a language that had been using such constructions without problem — as it still does.
Respected literary works throughout English history, including the King James Bible and the plays of Shakespeare, have used these kinds of sentences as occasion demanded. You're guaranteed to find examples in assigned readings from your English lit courses. Does it seem wrong because it attaches to something in a previous sentence? So do "However" and "Therefore," both of which have been targets of grammar grumblers in the past. So do sentences that start with "So do."
Not every relative pronoun will work at the start of a sentence: You likely won't be able to get away with something like "He asked about the pocket watch. That I found." But you know it won't work because you can feel that it won't work; no need to memorize a rule.
Why would we want to write a "partial" sentence when we can rewrite to make a "complete" one? For flow. Flow, tone, and concision. What if Monty Python were to have started a sketch with "Now we will present something completely different" rather than "And now for something completely different"?
Does this mean that anything goes? Certainly not. There are many, many ways to write badly with "incomplete" sentences. Best not to do it to excess. Or chop up thoughts. That are better put together. There is much to be said. For coherence. But it does mean that you need not burden your prose with extra words or convoluted constructions just for the sake of syntactic box-ticking.