Is it required that all elements of Maariv / Havdalah at the conclusion of Shabbos come after dusk, or may some part come between sunset and dusk?
If you really need to, you can say Maariv and Havdalah (omitting the blessing on the candle) from Plag HaMincha (1.25 hours before sunset) (ShA OC 293:3) just as much as you can say Maariv and Kiddush after that time on Friday. The blessing on the candle can be recited separately after nightfall. All labor remains forbidden until after nightfall (even after saying Havdalah!).
However, this should not be done ordinarily for it looks really weird (MA, Bach ibid.), there is a Mitzva to delay Havdalah in order to add on to Shabbat (ShA ibid. :1) (plus the leniency to daven Maariv early on Friday is even weaker without the advantage of adding on to Shabbat (Mishna Berura ibid. :9)), and people may come to perform forbidden labor before nightfall (ibid.).