Note: I was so concerned with getting started on my book early today that I forgot to blog. So sorry for being a bit late. /facepalm
So, for you to better understand how Propp’s Fairy Tale Functions serve a story, here is a summary of Stardust with the correlating functions in parenthesis:
The English village of Wall lies near a stone wall that is the border with the magical kingdom of Stormhold. A guard is constantly posted at a break in the wall to prevent anyone from crossing. At the beginning of the story, Dunstan Thorne crosses over the wall and into the Wall Market. There, he meets an enslaved princess who offers him a glass snowdrop in exchange for a kiss. Nine months later, the Wall Guard delivers a baby to Dunstan, saying his name is Tristan.
Eighteen years later, Tristan is living in Wall, working as a shop boy (0. Initial Situation). He lives with his father, his mother unknown to him (1. Absentation).
Meanwhile, in the royal palace of Stormhold, the king is on his deathbed. He throws a ruby into the sky, decreeing that the first of his fratricidal sons to recover it will be the new king. The gem collides with a star, and they fall together and land elsewhere in Stormhold. The king's two remaining sons, Primus and Septimus independently search for the gem.
In Wall, Tristan Thorne sees the star fall behind the wall, and vows to retrieve it (10. Beginning Counter-Action and 25. Difficult Task) for the object of his infatuation, Victoria, in return for her hand in marriage, but only if he retrieves it before Humphrey returns to Wall. Tristan attempts to cross the wall, but the Wall Guard tells him no one crosses the wall (2. Interdiction). Tristan tries to trick the Wall Guard, but fails.
His father reveals to him that his mother is from the other side of the wall (12. First Function of the Donor), and gives him a Babylon candle that she had left for him (14. Receipt of a Magical Agent), which instantly transports the user to any desired location. Tristan lights it (13. Hero’s Reaction) and is transported to Stormhold (3. Violation of Interdiction, 11. Departure, and 15. Guidance), to the fallen star, a beautiful woman named Yvaine. He promptly chains her in order to take her home to Victoria.
Three ancient witches in Stormhold also learn of the fallen star and resolve to find her, intending to eat her heart in order to recover their youth and replenish their magical power. The leader of the witches, Lamia, consumes the remains of the heart they had cut from a star that had fallen centuries before and was captured by the witches. Regaining temporary youth, Lamia hunts down Yvaine using her runes (4. Reconnaissance) and sets a trap for her, magically conjuring an inn in the countryside (6. Trickery).
Yvaine is weary and unaccustomed to daytime travel, so Tristan chains her to a tree and promises to return with food. In his absence, a unicorn frees Yvaine, then unwittingly takes her to Lamia's inn (7. Complicity). Tristan discovers Yvaine gone and lies down to rest. The stars whisper to Tristan (5. Delivery), warning of Yvaine's danger and begging him to save her as the last star who fell was murdered by the three witches and her heart eaten(8. Villainy or Lack); instructing him to get on a passing stagecoach, which happens to be Primus' (9. Mediation, the Connective Incident).
Tristan and Primus arrive at the inn, interrupting Lamia's attempt to kill Yvaine (16. Struggle). Lamia kills Primus, but Tristan and Yvaine escape using the stub of the Babylon candle (18. Victory and 19. Liquidation). Because they are each thinking of their respective homes, the candle takes Tristan and Yvaine into the storm clouds, between the earth and the stars, where they are captured by pirates in a flying ship. They befriend the kind-hearted Captain Shakespeare (22. Rescue), who gives him and Yvaine clean clothing (23. Unrecognized Arrival). He teaches the disguised Tristan how to fence and fight.
Septimus arrives at the site of the inn and discovers that he is the last surviving son of the king, only needing to find the stone to claim the throne. He learns that it is in the possession of the fallen star and that the heart of a star grants immortality (21. Pursuit and 24. Unfounded Claims).
After leaving Captain Shakespeare's ship, Tristan and Yvaine make their way to a village near the wall (20. Return)., where they spend the night at an inn. Come morning, Tristan leaves Yvaine sleeping and goes to Wall, bringing with him a lock of her hair, to tell Victoria that he won't marry her, having fallen in love with Yvaine (26. Solution and 27. Recognition). When the lock turns to dust, he realizes that Yvaine will die if she crosses the wall, and he rushes back to save her.
Yvaine wakes up to find Tristan gone, and she starts walking toward the wall, believing that he abandoned her to go back to Victoria. Tristan's mother, the princess, notices Yvaine walking to her doom, so she takes the caravan of her enslaver, a witch named Ditchwater Sal, to the wall to stop her. Lamia arrives and, after killing Sal, captures both her and Yvaine, taking them to the witches' castle.
Septimus and Tristan both pursue Lamia and meet at the castle, agreeing to work together for the time being. Barging into the witches' castle, Septimus recognizes the princess as his long-lost sister, Una. Una and Tristan meet for the first time, and she informs him that she is his mother.
Septimus and Tristan fight the witches, killing two of them, but Lamia kills Septimus using a voodoo doll, then uses it to make his corpse fight Tristan. Tristan disposes of the corpse. Lamia then disarms Tristan in a swordfight and is about to finish him off, when she breaks down over the loss of her two sisters. Lamia seemingly frees Yvaine but instead reveals her feigned defeat to be a ruse meant to bolster Yvaine's broken heart (28. Exposure). As the witch-queen bears down on them, Yvaine realises that Tristan's return has left her heartbroken no more. She tells him to close his eyes and hold her tight. As they embrace, her love for Tristan allows her to shine once again, vaporising Lamia in a blinding flash of pure starlight (30. Punishment).
Tristan retrieves the jewel that Yvaine was wearing. Una explains that, as her son, Tristan is the last male heir of Stormhold (29. Transfiguration). Tristan becomes the new king with Yvaine as his queen (31. Wedding). Later, after eighty years of ruling Stormhold, they both use a Babylon candle to ascend to the sky, where Tristan also becomes a star. Since Yvaine "gave her heart" to Tristan, the two will live forever in the sky.
Note: There is no instance of Branding in the film. Neither Tristan nor Yvaine are visibly wounded in the Struggle, nor do they receive any token for surviving it.