The gemara explains that Mordechai is called a Yehudi because he was kofer in avodah zara by not bowing down to Haman. What is the connection? Perhaps the answer to this question lies in understanding the source of the name Yehudi.
The medrash (Vayichi 98:6) explains that we are called Yehudi after Yehuda. This is the p'shat in the possuk "Yehuda ata yoducha achecha...ain adam omer reuveini ella yehudi".
The mefarshim on that possuk explain that this is the beracha in which Yaakov gives the malchus to Yehuda. The Klei Yakar adds further Yehuda merited to be king because he admitted that Tamar was correct and he did not let her die. The simple meaning then of this medrash is that the people of a kingdom are always referred to as subjects of their
king. Therefore, since Yehuda was the king of Klal Yisroel it is only natural that we are called Yehudi based on our king Yehuda. However, it would also come out that if the name Yehudi is derived from Yehuda, then in order to understand what Yehudi represents, we need to understand the qualities and characteristics of Yehuda himself.
The Qualities Of Yehudah
The gemara in Sotah (10b) says Yehuda received the malchus because he was mekadeish shem shamayim by admitting that Tamar was right. Rav Moshe Shapiro explains that HKBH is the king of the whole world. Klal Yisroel are his peopel. Therefore, the role of Klal Yisroel is to spread the kovod of HKBH in this world, just like the role of any loyal subject is to raise up the name of his king. It would come out, that if this is the role of Klal Yisroel, then the king of Klal Yisroel should be the one who best exemplifies this trait.
The ultimate form of being megaleh kovod shamayim is by being omekadesh shem shamayim. The gemara in Sotah is telling us that this was the quality that Yehuda possessed. By the story of Tamar, Yehuda could have kept quiet and noone would have known the difference. However, Yehuda understood that the correct thing to do was to admit the truth. The rotzon Hashewm was to admit that Tamar was right, and by following the rotzon Hashem Yehuda was mekadesh shem shamayim. Since it was Yehuda who demonstrated this quality, he was the one chosen to be the king and to lead Klal Yisroel in bringing forth kovod shamayim in this world.
Now we can understand why Mordechai is called Mordechai HaYehudi. There is nothing that stands in the way of HKBH's honor and limits the malchus of HKBHlike avodah zarak. One who worships a false idol is in effect saying that he doesn’t believe that Hashem runs the world by Himself and Hashem can’t do it without the assistance of these false the glory of HKBH to this world and is mekadesh shem shamayim to the entire world. Such a person deserves to be called a Yehudi.