These quote are all from Rambam's Mishne Torah, so it might be different according to other authorities. The first thing to determine is when Shabbat ends:
הלכות שבת פרק ה,ד
משתשקע החמה עד שייראו שלושה כוכבים בינוניים, הוא הזמן הנקרא בין
השמשות בכל מקום; והוא ספק מן היום, ספק מן הלילה, ודנין בו להחמיר, בכל
מקום. ולפיכך אין מדליקין בו; והעושה מלאכה בין השמשות שבת ובין השמשות
במוצאי שבת, בשוגג--חייב חטאת מכל מקום. וכוכבים אלו--לא גדולים הנראים
ביום, ולא קטנים שאין נראין אלא בלילה; ומשייראו שלושה כוכבים אלו
הבינוניים, הרי זה לילה ודאי.
From sundown till three medium stars are seen, is the time which is
called twilight in every place; and it is doubtful if it is day,
doubtful if it is night, and the law is to be strict in every place.
And accordingly, we don't light during twilight; and one who does
melacha during twilight prior to Sabbath or twilight after Sabbath, by
mistake -- must bring a sin offering in every place. And these stars
aren't the large ones which can be seen by day, or the small ones
which can be seen only at night [ i.e. in total darkness ]; and once
three medium stars have been seen, it is certainly night.
So first of all once three medium stars have been seen ( or could be seen ) the Shabbat day is certainly over and it would seem to imply that the biblical punishments for doing melacha on Shabbat would no longer apply.
Now why do we say Havdalah?
הלכות שבת פרק כט,א
מצות עשה מן התורה, לקדש יום השבת בדברים--שנאמר "זכור את יום השבת,
לקדשו" (שמות כ,ז), כלומר זוכרהו זכירת שבח וקידוש; וצריך לזוכרהו
בכניסתו, וביציאתו--בכניסתו בקידוש היום, וביציאתו בהבדלה.
It is a positive commandment from the Torah, to sanctify the Sabbath
with certain acts -- as it is said, "remember the Sabbath day, and
sanctify it", namely commemorate it in an honorable and sanctified
way; and one must commemorate it's beginning, and it's end -- at it's
beginning with Kiddush and at it's end with Havdalah.
We say it in order to fulfill the commandment of commemorating the Sabbath, just as the Sabbath begins whether or not we say Kiddush, it ends whether or not we say Havdalah.
הלכות שבת פרק כט,ה
אסור לאדם לאכול או לשתות יין, משיקדש היום--עד שיקדש. וכן משייצא היום,
אסור לו להתחיל לאכול ולשתות, ולעשות מלאכה, או לטעום כלום--עד שיבדיל;
ולשתות המים, מותר. שכח או עבר, ואכל ושתה קודם שיקדש או קודם
שיבדיל--הרי זה מקדש ומבדיל, אחר שאכל.
It is forbidden for a person to eat or drink wine, from the time
Sabbath starts -- until he sanctifies it. And also from when the
Sabbath ends, one is forbidden to start to eat or drink, and to do
melacha, or to taste anything -- until he makes a separation ( does
havadalah ); and to drink water is permitted. He forgot or
disregarded it, and ate and drank before doing Kiddush or before
making Havdalah -- the person makes Kiddush or Havdalah after they
finish eating.
It seems to me that we have a prohibition of melacha here which is specifically tied to the commandment of making Havadalah, since the Sabbath has already finished and together with it the prohibition of melacha which carries the death penalty.
So how do we fulfill the biblical requirement of Havdalah so that we may eat and do melacha?
הלכות שבת פרק טכ,ו
ו מדברי סופרים לקדש על היין, ולהבדיל על היין. ואף על פי שהבדיל
בתפילה, צריך להבדיל על הכוס; ומאחר שיבדיל ויאמר בין קודש לחול, מותר לו
לעשות מלאכה, אף על פי שלא הבדיל על הכוס.
And there is a Rabbinic requirement to make Kiddush on wine, and to
make Havdalah on wine. And even though he made Havdalah in the
prayers, he needs to make Havdalah on a cup; and as soon as he made
Havdalah and said, "between the holy and profane", he's permitted to
do melacha, even if he hasn't made Havdalah on a cup.
So as soon as he has said, "between the holy and profane" during his prayers he fulfills the biblical requirement of Havdalah and is allowed to do melacha. So what prayer is being referred to here?
הלכות תפילה פרק ב,ד
וכן במוצאי שבתות וימים טובים--אינו מתפלל הביננו, מפני שצריך לומר הבדלה
בחונן הדעת.
And also on Motzai Shabbaths and Yom Tovs -- one does not pray
"havi'nenu", because one must say Havdalah in "Chonen Ha'Da'at".
