Gemara

(Beraisa) Suggestion: Perhaps "...Al Nefesh Mes Lo Yavo" means even an animal, which is called "Nefesh Behemah"!

Rejection #1: "Al Nefesh Mes" refers to a person.

Rejection #2 (R. Yishmael): We need not learn from there. "Lo Yavo" discusses a Tum'ah imparted by entering (an Ohel).

4b (Beraisa - R. Yehudah): A Nazir Shimshon may become Tamei Mes, like Shimshon did.

Question: How do we know that Shimshon became Tamei?

Answer #1: We learn from "I killed 1000 men with the jawbone of a donkey".

Rejection: Perhaps he threw it at them without touching them, and never became Tamei!

Yevamos 60b (Beraisa - R. Shimon): The graves of Nochrim do not have Tum'as Ohel (they do not Metamei what towers above them. Regarding Tum'as Ohel it says "Adam Ki Yamus b'Ohel", and) it says "you are My flock... you are Adam";

You (Yisrael) are called Adam, but Nochrim are not called Adam.

Question: "Whoever killed a soul (in the war against Midyan) and touched a Mes will become Tahor." (This shows that a dead Nochri is Metamei!)

Answer #1: Perhaps a Yisrael died.

Chachamim do not accept this answer, for it says "V'Lo Nifkad Mimenu Ish";

R. Shimon holds that this means that no one stumbled in sin.

Answer #2 (Ravina): Nochri graves are excluded from Tum'as Ohel. They are not excluded from Tum'ah of carrying or touching!

Bava Metzia 114b - Rabah bar Avuha (to Eliyahu): Aren't you a Kohen (Pinchas)? Why are you in a cemetery (of Nochrim)?!

Eliyahu (Beraisa - R. Shimon): Graves of Nochrim do not impart Tum'as Ohel. "Adam Atem" - Yisrael are called 'Adam', Nochrim are not.

Rishonim

Rambam (Hilchos Evel 3:3): A Nochri is not Metamei b'Ohel. Therefore their graves are Tehorim. A Kohen may enter there and trample on their graves. It is forbidden only to touch or carry Tum'ah (of a dead Nochri).

Re'em (cited in Hagahos Maimoniyos 2): The Halachah follows R. Shimon, and Nochrim do not have even Tum'as Maga or Masa. We learn from Nazir 48a. R. Yishmael expounds that if a Mes is not Metamei b'Ohel, it is not Metamei through Maga or Masa. The Tana who argues agrees that a Nazir must be concerned only for Mesim like his father and mother, i.e. Yisraelim. He need not be careful about dead Nochrim; the same applies to Kohanim. One may rely on this, but it is better to be concerned for the stringent opinion.

Rebuttal (Hagahos Maimoniyos 2): The Sugya in Yevamos proves that Nochrim are Metamei b'Maga and Masa, like the Rambam.

Defense (Mishneh l'Melech 1 DH v'Ra'isi): Surely, the Re'em knew the Sugya in Yevamos! He agrees that Nochrim are Metamei b'Maga and Masa. He says only that since Kohanim are not commanded about Tum'as Ohel of Nochrim, they are not commanded about Maga and Masa of them. The Rambam holds that Chachamim of R. Yishmael hold that Tum'as Maga and Masa does not depend on Tum'as Ohel. Alternatively, even R. Yishmael holds that the verse excludes only animals, which have no Tum'as Ohel at all. Many Tum'os that are not Metamei b'Ohel are forbidden to a Nazir and break Nezirus, e.g. a small bone. Surely R. Yishmael agrees! The Re'em holds that if a body has Tum'as Ohel, Maga and Masa apply even to parts without Tum'as Ohel.

Mishneh l'Melech: Chachamim forbade Kohanim to go to Chutz la'Aretz (Avodah Zarah 13b). They decreed Chutz la'Aretz to be Tamei because Nochrim bury their dead anywhere. According to the Re'em, there is no Tum'ah at all! It is difficult to say that Chachamim decreed, but R. Shimon did not. Perhaps the Re'em holds like the opinion in Tosfos (Nazir 54b DH Eretz) that they decreed due to the many Yisraelim killed in Chutz la'Aretz.

Minchas Chinuch (263 DH v'Hinei ha'Lashon): The Gemara (Yevamos 61a) says that Nochri graves have no Tum'as Ohel. This implies that they have Tum'as Maga. If so, why did Eliyahu walk over them? Some say that touching Kelim touching a Mes makes one Tamei for seven days! We must say that the Gezeras ha'Kasuv of Tum'as Kever is only for a Mes with Tum'as Ohel.

Nimukei Yosef (Bava Metzia 69b DH Ashkechei): Even though Nochrim have Tum'as Masa, Eliyahu knew that there were no bones where he walked.

Rambam (Hilchos Tum'as Mes 1:13): A Nochri is not Metamei b'Ohel. This is a tradition. Regarding the war with Midyan it says 'anyone who touched a corpse'.

Rambam (9:4): The coffin of a Nochri is not Tamei, since a Nochri has no Tum'as Ohel. One becomes Tamei only through touching or moving the Tum'ah itself.

Rosh (Teshuvah 30:1): Poskim argue about Nochri graves. Rabbeinu Meir protested against Kohanim who walked over Nochri graves. One who is stringent will be blessed.

Poskim

Shulchan Aruch (YD 372:2): It is proper that a Kohen be careful not to walk over graves of Nochrim.

Note: The Beis Yosef (starting with DH Kivrei) brings the opinions of the Rambam, Rosh and Re'em, and says 'l'Halachah we are stringent.' The Darchei Moshe ha'Aruch and Shach explain that the Beis Yosef rules like R. Shimon, and we are stringent like the Rambam against the Re'em. The following laws in the Beis Yosef are according to R. Shimon. However, the Mishneh l'Melech (Evel 3:3) says that the Beis Yosef is stringent like the Rosh, and so he rules in the Shulchan Aruch.

Rema: This is even though some are lenient. It is proper to be stringent.

Or Some'ach (Tum'as Mes 1:13): The Gra (Aderes Eliyahu 19:18) says that in Parashas Chukas, "Kever" refers to the Kever of a Nochri. It is Metamei b'Maga but not b'Ohel. I.e. there is Tum'as Maga directly above the Mes, but the rest is Tahor. This refers to Tum'ah Retzutzah, i.e. the gap above the Mes is less than a Tefach. It is as if the Mes touches the cover. This is like how Rashi (Chulin 125b DH d'Kulah) explains why Tum'as Ohel joins with Maga. When something towers above Tum'ah, it is as if the entire space in between is filled with Tum'ah. Therefore, (even according to R. Shimon) Kohanim should be careful not to tower above Tum'ah Retzutzah, for it is like Maga.

Dagul me'Revavah: The Ra'avad (Nezirus 5:17) holds that a Tamei Kohen is not commanded against exposing himself to Tum'ah. Even though the Halachah does not follow the Ra'avad, Kohanim may rely on it regarding Nochrim, for this is a Sefek-Sefeka. Even if the Halachah does not follow the Ra'avad, perhaps the Halachah follows R. Shimon. The Mishneh l'Melech (ibid.) says that this does not apply to Tum'as Maga and Masa (for which the Re'em is lenient), for then both Sefekos are minority opinions. Perhaps we may rely on it regarding Tum'as Ohel, especially since the Lechem Mishneh says that Rashi holds like the Ra'avad.

Retraction (Dagul me'Revavah): Perhaps the Ra'avad only says that a Kohen is not lashed if he was already Tamei, but he agrees that it is forbidden. Therefore, a Kohen should not rely on this.