Is Brienne a traitor for pledging fealty to Catelyn Stark? Why did she do it?

Question

House Tarth is associated with House Baratheon. Does Brienne pledging fealty to House (Stark / Tully) make her an outright traitor?

What is the connection between Brienne and Catelyn? They met only once. It was a very frantic 5-min (or less) discussion that happened in Renly's tent after his assassination.

Brienne seems like a character who always wants to be pledged in fealty to someone, but it doesn't really matter who. Catelyn just happened to be standing next to Brienne when Brienne needed to pledge fealty again to someone after Renly's death?

Answer 1

Brienne was already considered (or would have been) a traitor if she had stayed. Renly's death would have been pinned on her. Nobody (Except Catelyn, who was there to witness it) would have believed her story about the "shadow in the shape of Stannis".

In essence Brienne only had one option... to go with the one person who would believe and protect her.

Answer 2

Legal technicalities

Other than what Skooba has mentioned, there's one other thing to consider. The legal loopholes are an alternative explanation.

House Tarth was sworn to House Baratheon of Storm's End and held the Isle of Tarth in the name of Lord of Storm's End.

Yet, Why does that mean that Brienne owes her fealty to House Baratheon? She is not the Lady of Tarth yet and has therefore no inherent allegiance to the Lord of Storm's End. That's for her father to do, Lord Selwyn Tarth. When Lord Selwyn dies, only then Brienne becomes a vassal of Lord of Storm's End.

Until then, she is a free agent who can swear fealty to anyone she likes. It is in any case not a definite thing that Brienne will remain heir to Lord Selwyn. If Lord Selwyn sires a son, that means Brienne is no longer the heir as sons come before daughters in succession.

And of course there's the matter of her vows as a Rainbow guard as well.

Brienne's personal preference and Vows as a Rainbow guard

Also there is personal preference as well. Brienne does not want to be Lady of Tarth. She only wants to be a Knight. Remember, she was a Rainbow guard of Renly, equivalent to King's Guard. King's Guard forfeit their claims on all lands and titles when they swear their vows. So in any case, after swearing her vows, Brienne is plausibly no longer the heir to Tarth Isles and is therefore not obligated to swear fealty to Lords of Storm's End.

How and why she swore fealty to Catelyn?

Brienne did not right away pledge fealty to Lady Catelyn as you suggest. She wanted to show her gratitude by safely escorting her to Riverrun and then return to Stormlands to avenge Renly Baratheon. But Catelyn convinced her that Brienne's attempts will be futile as of then so she should instead serve her son, Robb, who will most likely face Stannis sooner or later.

Brienne however preferred to swear fealty to Catelyn instead because Robb was a stranger to her and she had come to admire Catelyn.

As shown in the Season 2 Episode 5, The Ghost of Harrenhal:

Brienne: Once you're safely back amongst your own people, will you give me leave to go, My Lady?

Catelyn: You mean to kill Stannis.

Brienne: I swore a vow.

Catelyn: But Stannis has a great army around him. His own guards are sworn to keep him safe.

Brienne: I'm as good as any of them. I should never have fled.

Catelyn: Renly's death was no fault of yours. You served him bravely.

Brienne: I only held him that once as he was dying.

Catelyn: He's gone, Brienne. You serve nothing and no one by following him into the earth. Renly's enemies are Robb's enemies as well.

Brienne: I do not know your son, My Lady... but I could serve you if you would have me. You have courage. Not battle courage, perhaps, but, I don't know, a woman's kind of courage. And I think that when the time comes, you will not hold me back. Promise me that you will not hold me back from Stannis.

Catelyn: When the time comes, I will not hold you back.

Brienne: Then I am yours, My Lady. I will shield your back and give my life for yours if it comes to that. I swear it by the Old Gods and the new.

Catelyn: I vow that you shall always have a place in my home and at my table and that I shall ask no service of you that might bring you dishonor. I swear it by the Old Gods and the new.

As evident from this conversation, Brienne swore fealty because:

1. She admired Catelyn's courage.
2. She understood the futility of her cause.
3. Starks provided her a hope for avenging Renly.
4. She had plausibly forfeited her claims on her family lands after swearing vows of Rainbow guard.

Books perspective

In the books however, it is traditional that the Lords and their heirs owe their fealty to their overlords. It is evident from the conversation of Ser Robar Royce¹ and Catelyn Stark:

“You are a long way from the Vale, ser,” she told him.

“And you far from Winterfell, my lady.”

“I know what brought me here, but why have you come? This is not your battle, no more than it is mine.”

“I made it my battle when I made Renly my king.”

“The Royces are bannermen to House Arryn.”

“My lord father owes Lady Lysa fealty, as does his heir. A second son must find glory where he can.” Ser Robar shrugged. “A man grows weary of tourneys.”
_{A Clash of Kings - Chapter 31 - Catelyn III}

But in any case, since most probably Brienne is no longer heir to the Isles of Tarth, she owes no fealty to her father's overlord.

---

_{1. Robar Royce was second son of Lord Yohn Royce of Runestone, a prominent vassal to House Arryn of Eyrie}