I was taught that a sentence must have a verb. Must it? Why? Is it so in all languages?

No.

I was taught that too, that the components of a sentence were the subject and the verb.
I've never thought about other languages before, it's an interesting question.

Life!

In formal English, the shortest possible complete sentence is either an imperative command such as "Leave!" or a sentence with a subject and verb such as "He lies."

No, a sentence doesn't have to have a verb. First, there are so-called incomplete or elliptical sentences like "What?" or "Thanks a lot" or "More coffee?". Generally, you can easily reconstruct a complete sentence with a predicate ("What did you say?" and "Would you like more coffee?"), except with interjections (like "Hi!" or "Ouch!", with "Thanks!" as a borderline case).

But in some languages, even complete sentences don't have to express the predicate "to be". For example, in Wolof you would say "Maa ngi fi"* to say "I am here". It is composed of "maa ngi" (a form of the personal pronoun "I") and "fi" ("here"). The verb ("nekk", in case you're interested) is not expressed, but it is implied. I think the same happens in modern Russian, maybe someone can elaborate on that? I have no idea if any other verbs are regularly omitted in any language; my guess is that they aren't, since they carry an essential part of the content of a sentence, and generally verbal forms also encode tense, aspect, mood and voice (although this information may be encoded by other means as well).

*This is actually a standard reply to "how are you?", meaning "I'm fine".

No, a sentence doesn't have to have a verb. First, there are so-called incomplete or elliptical sentences like "What?" or "Thanks a lot" or "More coffee?". Generally, you can easily reconstruct a complete sentence with a predicate ("What did you say?" and "Would you like more coffee?"), except with interjections (like "Hi!" or "Ouch!", with "Thanks!" as a borderline case).

That is why I made the distinction between formal and colloquial English.

^^Yes sorry, I only saw your post later. Still, even in formal English, some incomplete sentences are possible (note that incomplete is a technical term and doesn't mean ungrammatical or incorrect or anything like that):
"Goodbye!"
"Yours sincerely"
And of course, short questions and answers:
"I think I can manage this. - How?"
"Where have you been? - In the library."
Of course, these need some context. But then, any linguistic phenomenon can only be properly discussed in context.

"In the library" isn't exactly something which one would write or speak formally as a sentence. It's an aspect of colloquial conversation to answer questions solely with a prepositional or independent clause. Greetings and salutations are exceptions in all facets of speech and writing, of course.

katja z wrote: Still, even in formal English, some incomplete sentences are possible (note that incomplete is a technical term and doesn't mean ungrammatical or incorrect or anything like that):
"Goodbye!"
"Yours sincerely"

But these are abbreviations too, from "God be with you" and "I am yours."

I asked the question because I was thinking about signs without grammar - a middle finger, blowing a kiss, rolling eyes etc and wondering how the same function can be served by formal language. Even though it derives from a full sentence perhaps "goodbye" is now such a sign, like "ciao," (the etymology of which I don't know).

logical bob wrote:

katja z wrote: Still, even in formal English, some incomplete sentences are possible (note that incomplete is a technical term and doesn't mean ungrammatical or incorrect or anything like that):
"Goodbye!"
"Yours sincerely"

But these are abbreviations too, from "God be with you" and "I am yours."

Yes diachronically speaking they are derived from full sentences, but from the point of view of the modern language (synchrony), they are full verbless expressions in their own right.

I asked the question because I was thinking about signs without grammar - a middle finger, blowing a kiss, rolling eyes etc and wondering how the same function can be served by formal language. Even though it derives from a full sentence perhaps "goodbye" is now such a sign, like "ciao," (the etymology of which I don't know).

The gestural examples you give are closer to interjections, most of which are not abbreviations of "full" sentences, even diachronically, but independent vocalizations (think "Ouch!"). They are a close vocal analogue of (conventional) gestures - gestural and vocal communication do share a number of traits and are typically closely linked in face-to-face communication (not in writing though, which is why we use a number of punctuation signs to make up for the absence of gestures and intonation to organise and clarify linguistic utterances). These vocalisations ("vocal gestures"?) stand outside the morphosyntactic system, just like gestures, but unlike these, they can be pulled into syntax: "He ah'ed and hmm'd and finally said that he would think about it." As to the question whether they constitute a sentence, it depends on how you define a sentence, but they do constitute independent utterances and bear the conventional marks of a sentence in writing (capital letter at the beginning, end punctuation mark).

Oh, and "ciao" comes via Italian from a Venetian phrase meaning "(I'm) your slave".

katja z wrote:These vocalisations ("vocal gestures"?) stand outside the morphosyntactic system, just like gestures, but unlike these, they can be pulled into syntax: "He ah'ed and hmm'd and finally said that he would think about it."

At last, a sound grammatical function for "and I was like..."

Thanks katja. I'm duly embarrassed to be having the workings of the only language I know explained to me by someone who learnt it as a foreign one.

logical bob wrote:
Thanks katja. I'm duly embarrassed to be having the workings of the only language I know explained to me by someone who learnt it as a foreign one.

No problem. If it's any help, my remarks weren't specifically about English but about languages in general, I just used English to illustrate them.

ETA: Oh, and I forgot to mention that many exclamatory sentences are verbless too:
"What a wonderful idea!"
"What a pity!"

The various types of exception to the general rule of thumb stated in the OP are grouped under the umbrella term "minor sentences".