How do we know that the prohibition against doing m'lacha on chagim begins at sunset and not dawn?
The Torah spells out (Lev. 23:32) that Yom Kippur begins בתשעה לחדש בערב, in the evening of 9 Tishrei, and that it runs מערב עד ערב, from evening to evening.
As explained by the Gemara, Rosh Hashanah 9a, the words בתשעה לחדש בערב teach us that מוסיפין מחול על הקדש - we have to start Yom Kippur a little earlier than sunset and end it a little after nightfall. The final words of the verse, תשבתו שבתכם, tell us that the same applies to Shabbos and all of the other Yamim Tovim (all of which are collectively called Shabbos, as in ממחרת השבת in connection with Sefiras Haomer). So we see that all of them begin and end at the same time.