It's probably no surprise that George R. R. Martin, who wrote for the TV show "Beauty and the Beast," really seems to like this fairy tale and has included two major Beauty and the Beast stories in A Song of Ice and Fire, those of Brienne of Tarth and Jaime Lannister, and Sansa Stark and Sandor Clegane.
Catelyn (and the readers) meet Brienne at Renly’s tournament at Bitterbridge; before Brienne ever speaks a line of dialogue, we (and Catelyn) are informed that this woman is mockingly called “Brienne the Beauty” (in the same way that a giant might be called “Tiny.”)
"That's Brienne of Tarth, daughter to Lord Welwyn the Evenstar."
"Daughter?" Catelyn was horrified
"Brienne the Beauty, they name her ... though not to her face, lest they be called upon to defend those words with their bodies.
Catelyn also notices Brienne’s eyes, foreshadowing Jaime’s noticing them. And this is imo, very, very deliberate, because of that unattributable but very popular quote about eyes being the windows to your soul.
Beauty, they called her ... mocking... Brienne's eyes were large and very blue, a young girl's eyes, trusting and guileless, but the rest ...
Catelyn, who sees elements of Sansa and Arya in Brienne, is wonderfully motherly and kind to this girl whose inability to fit into the norms of society is so manifest. She is with Brienne when Renly - the first man Brienne has loved - is murdered by the sorcery of a devotee of Rh’llor, and dissuades Brienne from fruitlessly seeking revenge against Stannis that will only lead to Brienne’s own death. Brienne, whose habit is to recklessly pledge her life and allegiance to anyone who’s kind to her, says her vows as Catelyn’s sworn sword, putting her on the tragic path to meet Catelyn’s horrifying revenant, Lady Stoneheart, who was raised from the dead by a devotee of Rh’llor, and, who in her quest for vengeance, makes Brienne swear a heartbreaking oath to kill the man she loves, in order to save the life of an innocent.
At Riverrun, Catelyn, who comforted Brienne in her grief for Renly, tells Brienne about Bran’s and Rickon’s supposed deaths - in fact, aside from the Riverrun Maester who gave Catelyn the message, Brienne is the only person in Riverrun who knows about Bran and Rickon at this point, just as Catelyn was the only witness besides Brienne to the shadow that killed Renly. Again, this is important. There are reasons why Catelyn, Brienne and Jaime form these alliances and connections and I really think Catelyn’s role in pushing Brienne and Jaime together cannot be understated. The dinner where Catelyn reveals this tragedy to Brienne is actually quite weird because Catelyn has this strange, dissociative conversation with Brienne, leaping from topic to topic, almost talking to herself. At one point, the reader is led to think that Catelyn will seek revenge on Jaime right then and there, since he is the only enemy who is within her power.
And then we get to the dungeon, and (sadly) the only scene Catelyn and Jaime share.
Jaime Lannister had been allowed no razor since the night he was taken in the Whispering Wood, and a shaggy beard covered his face, once so like the queen's. Glinting gold in the lamplight, the whiskers made him look like some great yellow beast, magnificent even in chains. His unwashed hair fell to his shoulders in ropes and tangles, the clothes were rotting on his body, his face was pale and wasted ... and even so, the power and the beauty of the man were apparent.

