dissenting.
HOLLOWAY, Circuit Judge.The United States appeals from the order of the district court dismissing the indictment which had been returned against defendant/appellee Ricardo Aguirre, charging him with illegal re-entry into the United States after having been deported, in violation of 8 U.S.C. § 1326(a),(b)(2). The district judge dismissed the charge based on her conclusion that the underlying deportation proceedings had been fundamentally unfair. United States v. Aguirre-Tello, 181 F.Supp.2d 1298 (D.N.M.2002). We have jurisdiction under 18 U.S.C. § 3731 and 28 U.S.C. § 1291 to review the district court’s dismissal of the indictment.
I
Defendant was born in Mexico in 1969. He testified in the hearing in the district court that he first came to the United States with his parents in 1973, and his counsel told the court that he had been in this country ever since. However, he was not in this country legally until August 1987, when he was granted an immigration visa. In November 1989, defendant was convicted in state court in California of attempted murder. He was sentenced to a term of nine years but was released after having served, it appears, just less than five years of that sentence.1 On his release from prison in 1994, the Immigration and Naturalization Service commenced deportation proceedings. A hearing was held before an Immigration Judge (IJ) on August 19, 1994, one day before defendant would have reached the legally significant milestone of seven years of legal residence in this country, as discussed below.
Because the issue in this appeal is whether the 1994 deportation hearing was fundamentally unfair, we will review the record of that proceeding in some detail.
II
The deportation hearing was held before an Immigration Judge (IJ) in El Centro, California, on August 19, 1994, for twenty potential deportees. Defendant Aguirre was one of three potential deportees who indicated that they spoke English and wanted their hearings conducted in English.
First, the IJ determined that all of the potential deportees understood that the purpose of the hearing was to determine if the charges were true and that each one *1185would be asked to admit or deny the charges. In his explanation of the hearing the IJ said, “Even if the charges are proven [that] doesn’t mean you must be deported; you might be eligible for some pardon or for asylum. If you are eligible for a pardon, I will tell you. Do you understand the purpose of this hearing?” The transcript shows that the defendants as a group answered “yes.”2
The IJ then informed the potential deportees that they had a right to be represented by counsel:
At this hearing, you can have an attorney, but the government won’t pay for your attorney. You each have a list of free legal services. If you haven’t had time to consult with an attorney, I’ll postpone your case. But you don’t have to have an attorney; you have the right to represent yourself. Do you understand your right to be represented?
ALL DEFENDANTS: Yes.
Aplt.App. at 7-8.
Later, the IJ further advised the potential deportees of their rights:
THE COURT: Do any of you want more time to get a lawyer? And if you do, raise your hand. There are no hands. So we’ll continue with each of you representing yourself. If you represent yourself, you should know that you can listen to and ask questions of any witness the government calls and look at anything the government gives me to consider against you. You can object to the government’s evidence by explaining to me why you disagree with it. You can call witnesses to testify for you and show me anything you believe is important to your case. You can testify and tell me your story in your own words. Do you understand these rights?
DEFENDANTS: Yes.
THE INTERPRETER: Yes, by all responses.
THE COURT: If you disagree with my decision, you can appeal. Your right to appeal is explained on the same paper that lists the legal services. By an appeal, you ask a higher court to review what I’ve done and determine if I’ve made a mistake. Do you understand your right to appeal?
DEFENDANTS: Yes.
THE INTERPRETER: By all respondents, yes.
ApltApp. at 13-14.
Later in the hearing, the IJ addressed Mr. Aguirre individually. After determining that Aguirre did not have an attorney, the IJ asked if he wanted more time to get an attorney. Aguirre said no. Aguirre affirmed that he understood his rights and that he understood the charges. He also admitted that he was a citizen of Mexico, that he had entered the United States as an immigrant in August 1987, and that in November 1989 he had been convicted of attempted murder in Los Angeles County, California. Aguirre also said that he had been sentenced to nine years in prison and had served 63 months.3
*1186As the colloquy between the IJ and Mr. Aguirre continued, the defendant testified that he was born in Mexico, that neither of his parents were American citizens at the time, that he had received a “green card” but had never applied for citizenship, and that he had lived in the United States for the last seven years. At that point, the IJ quite apparently realized two things: that it had been seven years less one day since Aguirre had been permitted to enter this country legally, and that under the law then in effect, aliens who had been in this country legally for seven years were eligible for a “waiver” or discretionary relief from deportation. Thus, the IJ advised Aguirre:
THE COURT: Okay. You are not today eligible for a pardon, but you would be tomorrow. Do you want your case postponed to see if you might be granted a pardon and allowed to remain in this country?
DEFENDANT AGUIRRE: No.
THE COURT: All right. If I order you deported, then, to what country do you want to go?
DEFENDANT AGUIRRE: Mexico. THE COURT: Do you know, sir, that if you’re deported, that you’ll lose your status in this country and you could not return except with a visa and proper permission from the Attorney General? DEFENDANT AGUIRRE: I do.
THE COURT: And do you know that your crime would make you ineligible for a visa to come back to the US? DEFENDANT AGUIRRE: Ido.
THE COURT: So that if you want to stay in the US, this is the time to, shall we say, fight it out and try to remain; do you understand that?
DEFENDANT AGUIRRE: I understand.
THE COURT: Now that you know all that, do you want to apply for a pardon? DEFENDANT AGUIRRE: No.
THE COURT: Why not?
DEFENDANT AGUIRRE: I want to voluntarily return to my country.
THE COURT: Okay. Well, there’s no voluntary return available in a case like this, but are you saying you just want to go back?
DEFENDANT AGUIRRE: That’s it. THE COURT: All right. Based on your statements to me, I find that you’ve knowingly, voluntarily and intelligently waived your opportunity for relief. And I order you deported to Mexico. You can appeal. Do you want to appeal? DEFENDANT AGUIRRE: No.
THE COURT: Then my decision’s final. Good luck, sir.
ApltApp. at 24-26.
Ill
The indictment in the instant case alleges that Aguirre was found in Dona Ana County, New Mexico, on or about February 10, 2001, and that he had not received permission from the United States Attorney General to apply for admission into this country after his 1994 deportation. ApltApp. 74. Defendant moved to dismiss the indictment, asserting that the 1994 deportation proceeding was fundamentally unfair and invalid on due process grounds. After a hearing on November 20, 2001, at which, inter alia, the tape of the 1994 deportation hearing was played and the defendant testified in person, the district judge determined that the 1994 deportation hearing had been inadequate to protect defendant’s rights in several ways.
The focus of the district court’s Memorandum Opinion and Order, ApltApp. at 164 et seq, is on the conclusion that the *1187deportation hearing had been unfair because the immigration judge had not adequately explained to defendant his unique circumstances and their import. Specifically, the law in effect at the time provided that an alien who had been lawfully in this country for seven years could apply for a waiver of deportation even though he had committed an aggravated felony, provided he had not served a prison term of five years. Such a waiver was then provided for in section 212(c) of the Immigration and Naturalization Act, which stated in pertinent part:
Aliens lawfully admitted for permanent residence who temporarily proceeded abroad voluntarily and not under any order of deportation, and who are returning to a lawful unrelinquished domicile of seven consecutive years, may be admitted in the discretion of the Attorney General.... The first sentence of this subsection shall not apply to an alien who has been convicted of one or more aggravated felonies and has served for such felony or felonies a term of imprisonment of at least 5 years.
8 U.S.C. § 1182(c) (1994).
As the district judge pointed out, although the statute refers to persons who temporarily leave the United States, it has been held that the section 212(c) waiver “is equally applicable to permanent residents who have never left.” See INS v. St. Cyr, 533 U.S. 289, 121 S.Ct. 2271, 2276, 150 L.Ed.2d 347 (2001). Defendant was only one day short of having completed such seven years on the day of the deportation hearing. As the excerpts from the deportation hearing above indicate, the IJ seemed to be aware of the importance of the fact that defendant was but one day short of seven years of legal residence, but in his explanation the IJ said that defendant would be eligible to apply for a “pardon” in one more day, rather than a waiver, and the IJ gave no further explanation of the nature of the relief for which defendant would have become eligible.
The district judge observed that immigration law is technical and complex to the point that it is confusing to lawyers, much less to laymen.4 She noted that explanations of rights in technical terms have been held to be inadequate, and she found that in this case the use of an everyday term actually was even more confusing. A pardon is a form of relief distinct from a waiver. The judge concluded that use of this term “pardon” did not convey to defendant the nature of the relief for which he was about to become eligible.
The judge also found that defendant had not been given a list of free legal services prior to the 1994 deportation hearing,5 nor had he been advised then that his bond had already been set at $20,000.6 This latter failure was exacer*1188bated by the fact that the previous deportee had been specifically advised of the possibility of bond, which could have caused defendant to believe that he was-not eligible for release. We are bound by the district judge’s findings that the list of free legal services was not furnished to Defendant Aguirre and as to the lack of advice to him on his bond having been set.
The judge noted that Tenth Circuit precedent requires that a defendant in these circumstances show not only that the underlying deportation proceedings had not been fundamentally fair but also that the deficiencies in the proceeding had worked to his legal prejudice. The district court noted that there appeared to be a slight difference between the Ninth and Tenth Circuit prejudice standards, but determined that the defendant in this case had shown prejudice under any standard.
The judge also concluded that defendant was not precluded from attacking the deportation order by his failure to take a direct appeal. She found that a waiver of appeal rights that is not “considered or intelligent” improperly deprives the person of judicial review of the deportation order, citing United States v. Mendozar-Lopez, 481 U.S. 828, 839-40, 107 S.Ct. 2148, 95 L.Ed.2d 772 (1987). The judge found that defendant’s waiver had not been considered and intelligent because the most likely avenue of’relief, for which he was to be eligible one day later, had not been explained to him.
IV
A
When a previous deportation proceeding is attacked on constitutional grounds, we are presented with a mixed question of fact and law which we review de novo. United States v. Meraz-Valeta, 26 F.3d 992, 997 (10th Cir.1994). Defendant has the burden of showing that the underlying deportation hearing was fundamentally unfair, and to do so he must show that he was prejudiced. Id. at 998. As part of this showing, he must establish that the unfairness of the deportation proceeding deprived him of his right of direct appeal. Id. We must afford the deportation proceeding a “presumption of regularity.” United States v. Arevalo-Tavares, 210 F.3d 1198, 1200 (10th Cir.2000).
*1189B
The government's first contention on appeal is that judicial review of the 1994 deportation proceeding is barred by defendant's failure to exhaust administrative remedies which were available to him then, a requirement which Congress imposed in 1996 and which is codified at 8 U.S.C. § 1326(d) (2000). The district court addressed this requirement sua sponte. As the district judge noted, one circuit court has held that this exhaustion requirement "cannot bar collateral review of a deportation proceeding when the waiver of right to an administrative appeal did not comport with due process." United States v. Muro-Inclan, 249 F.3d 1180, 1183 (9th Cir.2001). The district judge observed that our court has not decided this issue. The judge then concluded that the exhaustion requirement did not bar relief because the due process violations prevented defendant from exhausting his administrative appeals at the time of his deportation.
We agree with the district court and with the Ninth Circuit's holding in Muro-Inclan. The holding of United States v. Mendoza-Lopez, 481 U.S. 828, 837-39, 107 S.Ct. 2148, 95 L.Ed.2d 772 (1987), permits this due process challenge to the 1994 deportation hearing even though Congress did not intend to permit such challenges in prosecutions under 8 U.S.C. § 1326. And in Mendoza-Lopes, the Supreme Court also held that the respondents "were deprived of their rights to appeal, and of any basis to appeal since the only relief for which they would have been eligible was not adequately explained to them...." 481 U.S. at 842, 107 S.Ct. 2148 (emphasis added). We think it clear under this rea-sonirig that finding as we do in defendant's favor on the primary issue-that his due process rights were violated by the failure to give an adequate explanation of the discretionary relief available to him-the nature of this error was such as to deprive him of his right to any appeal, whether administrative or judicial, and that a deprivation resting on such a ground cannot bar his collateral attack in this proceeding.
Thus, we reject the government's contention that defendant's collateral attack is barred by the failure to exhaust administrative remedies.
C
The government contends that the district court erred in its conclusion that the failure to apprise defendant of the discretionary relief for which he was eligible at the 1994 deportation hearing rendered that hearing fundamentally unfair in violation of defendant's due process rights. The relief for which defendant was eligible in 1994 was a waiver of deportation by the Attorney General under section 212(c) of the Immigration and Naturalization Act of 1952 as amended in 1990, which has since been repealed but was then codified at 8 U.S.C. § 1182(c). A full explanation of the source of this potential relief was given in INS v. St. Cyr, 533 U.S. 289, 121 S.Ct. 2271, 2275-78, 150 L.Ed.2d 347 (2001), and need not be repeated here. It is sufficient to note that it was well established in 1994, and it is not contested here, that the Attorney General was authorized to waive deportation of a permanent resident alien who had lawfully resided in this country for seven years and had not served more than five years of imprisonment on a conviction for an aggravated felony. See id.
The primary problem in the underlying deportation proceeding, defendant contends, is that the IJ had a duty to adequately inform him of his eligibility for a waiver, and the reference to a "pardon" did not discharge that duty. A section 212(c) waiver of deportation is not interchangeable with a pardon. The procedures involved in obtaining a waiver, and *1190the discretion-guiding principles laid down for immigration judges to determine whether to grant a waiver demonstrate the significant distinction. In order to obtain a waiver, the applicant goes before an immigration judge and puts on his case to show that the positive equities outweigh the negative equities. See 8 C.F.R. §§ 3.0, 3.1(a)(1), (b)(3) & (d)(1) (1993); see also Yepes-Prado v. INS, 10 F.3d 1363, 1365-66 (9th Cir.1993). The immigration judge decides whether to grant a waiver, guided by the factors enumerated by various INS decisions. See, e.g., In re Edwards, 20 I. & N. Dec. 191, 195-96, 1990 WL 385757 (1990). After the immigration judge makes a decision, the applicant is entitled to appeal that decision to the Board of Immigration Appeals. See 8 C.F.R. § 3.1(b)(3) (1993). The BIA decision may then be appealed to the appropriate Circuit Court of Appeals. 8 U.S.C. § 1105a(a)(2) (1994). This is not at all like the concept or the practice of obtaining a pardon. Moreover, during the relevant years including 1994, the year of defendant’s deportation proceeding, the section 212(c) waivers were granted to a substantial percentage, just over one-half of those who applied for them. St. Cyr, 121 S.Ct. at 2277 & n. 5.7 Therefore, the suggestion by the immigration judge in this case that the defendant might be eligible for a pardon cannot discharge the duty to inform the defendant about his eligibility for a waiver.8
*1191The IJ was required to inform defendant of his apparent eligibility for section 212(c) relief because he had sufficient information before him to trigger his knowledge of that eligibility. See United States v. Mendoza-Lopez, 7 F.3d 1483, 1485 (10th Cir.1993), impliedly overruled on other grounds by United States v. Fagan, 162 F.3d 1280 (10th Cir.1998); see also Moran-Enriquez v. INS, 884 F.2d 420, 422 (9th Cir.1989); 8 C.F.R. § 242.17(a) (1994) (“The immigration judge shall inform the respondent of his or her apparent eligibility to apply for any of the benefits enumerated in this paragraph and shall afford the respondent an opportunity to make application therefor during the hearing.”).9 While we note that we have acknowledged this duty in our own circuit, more importantly the Ninth Circuit, in which defendant’s deportation hearing occurred, has held the INS regulatory language to be mandatory for immigration judges. See Moran-Enriquez, 884 F.2d at 422 (“We have held 8 C.F.R. § 242.17(a) to be mandatory; if an IJ fails to advise an alien of an avenue of relief potentially available to him, we will remand for consideration of the alien’s eligibility for that relief.”); cf. United States v. Muro-In-clan, 249 F.3d 1180, 1184 (9th Cir.), cert. denied, 534 U.S. 879, 122 S.Ct. 180, 151 L.Ed.2d 125 (2001) (“[W]hen the record before the [IJ] raises a reasonable possibility of relief from deportation under this provision, it is a denial of due process to fail to inform an alien of that possibility at the deportation hearing.”) (quotation omitted) (citing United States v. Arrieta, 224 F.3d 1076, 1079 (9th Cir.2000)). It seems clear from review of the transcript of the deportation proceedings that the IJ was well intentioned and made an affirmative effort to communicate to defendant the effects of failing to contest the proceedings. Nevertheless, his attempt to explain the relief to defendant was inaccurate and inadequate.
In addition, defendant may have been led to believe that bond was not available; in any event, it is undisputed that he was not told of the availability of bond in general, much less of the fact that bond had already been set in his case at $20,000. Finally, although as noted there is conflicting evidence in the record as to whether defendant was informed in 1994 that free legal services were available to him, this subordinate issue was one of fact, and the *1192district judge’s finding that defendant was not so advised is not clearly erroneous. See Memorandum Opinion and Order at 8, Aplt.App. at 171.
We conclude that the combination of these deficiencies did result in fundamental unfairness. Our conclusion, like that of the district court, is based primarily on the fact that the availability of discretionary relief, often granted under section 212(c), was not adequately explained.10 Here the IJ’s attempt to explain the relief available to defendant was not merely inadequate; it was misleading. It left Defendant Aguirre with the impression that a rare executive “pardon” was what he might hope for, instead of the very frequently granted “waiver” under section 212(c). See INS v. St. Cyr, 533 U.S. 289, 121 S.Ct. 2271, 2276-77, 150 L.Ed.2d 347 (2001) (“a substantial percentage,” just over one-half, of aliens’ applications for § 212(c) waivers have been granted).
D
1
To succeed in this collateral challenge, however, defendant must show more. As we have stated above, he must show that he was prejudiced and that he was thereby deprived of his right of direct appeal. Our earliest case requiring a showing of prejudice appears to be Michelson v. INS, 897 F.2d 465, 468 (10th Cir.1990). As far as we have been able to determine, however, we have never been required to decide specifically what this burden entails. In one case we said that the defendant had failed to show that, if he had been informed of his right to appeal, “the outcome of his case would have been different.” United States v. Meraz-Valeta, 26 F.3d 992, 998 (10th Cir.1994).
For several reasons, we do not believe that Meraz-Valeta imposed a standard under which the defendant would be required to show with complete certainty that he would not have been deported but for the procedural deficiencies in the underlying proceeding. First, it would be impossible in the context of this case to meet such a standard. At issue here is discretionary relief. No matter how compelling a showing one in the position of Mr. Aguirre were to make, the showing would never eliminate all possibility that the executive’s discretion to grant a waiver would not be exercised in his favor. This question arises only when, as here, a court has determined that a procedural shortcoming rises to the level of a deprivation of constitutional due process and fundamental fairness. For a defendant who previously had been deported under such circumstances to then be faced with an insurmountable barrier to obtaining relief would be a cruel irony and itself fundamentally unfair. For this reason alone, the government’s argument that the “would have been different” language from Meraz-Valeta is to be taken literally as establishing a standard of utter certainty is unpersuasive.
Due to the facts in Meraz-Valeta, the “would have been different” language was dictum. In Meraz-Valeta the defendant apparently was unable to show prejudice in any sense because there is no indication that he had alleged, much less made a showing, that there would have been any ground for appeal. Indeed, our research has not disclosed any case from this circuit in which the outcome might have been different depending on the standard used to determine if the defendant could show prejudice from the defects in a previous deportation proceeding. Moreover, and *1193more importantly, our opinion in Meraz-Valeta relied on United States v. Holland, 876 F.2d 1533, 1537 (11th Cir.1989), and specifically cited to "would have been different" language in that case. The Holland court actually articulated its intent by referring to "the possibifity of prejudice," and "could have made a difference. Id. In addition, the court stated: "The prejudice need not rise to the level of showing that the defendant would not have been deported, but rather that the errors might have affected the outcome of the hearing." Id. at 1536 (emphasis added). Thus, there was no adoption of a standard demanding certainty in Holland and, by inference, no adoption of such a standard by us in Meraz-Valeta.
A "might have" rather than a "would have" standard comports with the standards in all of the other circuits that have decided this question. The Ninth Circuit requires only "plausible grounds of relief which might have been available ... but for the deprivation of rights." United States v. Corrales-Beltran, 192 F.3d 1311, 1318 (9th Cir.1999). See also United States v. Jimenez-Marmolejo, 104 F.3d 1083, 1086 (9th Cir.1996). The First, Third, Fourth, Fifth, and Eighth Circuits have required a "reasonable likelihood" that but for the errors alleged, the outcome would have been different. See, e.g., United States v. Wilson, 316 F.3d 506, 511 (4th Cir.2003); United States v. Fellows, 50 Fed.Appx.82, 85 (3d Cir.2002); United States v. Benitez-Villafuerte, 186 F.3d 651, 658-59 (5th Cir.1999); United States v. Loaisiga, 104 F.3d 484, 487 (1st Cir.1997); United States v. Perez-Ponce, 62 F.3d 1120, 1122 (8th Cir.1995). The Second Circuit requires a prima facie showing that the defendant would have been eligible, and could have made "a strong showing" in support of his application. Rabiu v. INS, 41 F.3d 879, 882 (2d Cir.1994). All of these various standards comport with a "might have" standard, rather than a "would have" standard.
In United States v. Encarnacion-Galvez, 964 F.2d 402 (5th Cir.1992), the Fifth Circuit noted that its standard was consistent with that applicable in review of claims in criminal cases of ineffective assistance of counsel under Strickland v. Washington, 466 U.S. 668, 694-697, 104 S.Ct. 2052, 80 L.Ed.2d 674 (1984), which it viewed as analogous. 964 F.2d at 407. We agree that the analysis of prejudice in cases like the instant case is analogous to the analysis of prejudice under Strickland. Indeed, it is interesting to note that we have at times described the standard for showing prejudice under Strickland in the same shorthand-"would have been different"-when we clearly did not mean to distort the test which the Supreme Court had set out. In one case, we even used the two formulations in successive sentences:
Under the second [prejudice] prong, a petitioner must show that, but for counsel's errors, the result of the proceedings would have been different. If the alleged ineffective assistance occurred during the guilt stage, the question is whether there is a reasonable pro bability the jury would have had reasonable doubt regarding guilt. If the alleged ineffective assistance of counsel occurred during the sentencing phase, this court considers whether there is a reasonable probability that, absent the errors, the sentence would have con-eluded that the balance of aggravating and mitigating circumstances did not warrant death.
Moore v. Gibson, 195 F.3d 1152, 1178 (10th Cir.1999) (citations omitted; emphasis added).
In sum, we are convinced that the standard to apply in a case like Aguirre's is whether there is a reasonable probability that Aguirre would have obtained relief from deportation had the Immigration *1194Judge properly advised him about the waiver’s imminent availability as a recourse he could invoke.11
2
We proceed then to the question whether defendant has shown a reasonable probability that he would have obtained relief had the IJ adequately explained to him that the next day he would have been eligible for a waiver under section 212(c). The Board of Immigration Appeals has adopted what we may term an all-facts-and-circumstances balancing test to guide the exercise of discretion under this statute:
The exercise of discretion in a particular case necessarily requires ... a balancing of the social and humane considerations presented in an alien’s favor against the adverse factors evidencing his undesirability as a permanent resident.Favorable considerations have been found to include such factors as family ties within the United States, residence of long duration in this country (particularly when the inception of residence occurred at a young age), evidence of hardship to the respondent and his family if deportation occurs, service in this country’s armed forces, a history of employment, the existence of property or business ties, evidence of value and service to the community, proof of genuine rehabilitation if a criminal record exists, and other evidence attesting to a respondent’s good character. Among the factors deemed adverse to an alien are the nature and underlying circumstances of the exclusion or deportation ground at issue, the presence of additional significant violations of this country’s immigration laws, the existence of a criminal record and, if so, its nature, recency, and seriousness, and the presence of other evidence indicative of a respondent’s bad character or undesirability as a permanent resident of this country. Moreover, one or more of these adverse considerations may ultimately be determinative of whether section 212(c) relief is in fact granted in an individual case.
We also have pointed out that as the negative factors grow more serious, it becomes incumbent upon the alien to introduce additional offsetting favorable evidence, which in some cases may have to involve unusual or outstanding equities. [0]ne must examine the gravity of the offense per se. In addition, such a showing may be mandated because of a single serious crime.... We observe that an alien who demonstrates unusual or outstanding equities, as required, does not compel a favorable exercise of discretion; rather, absent such equities, relief will not be granted in the exercise of discretion.
In re Edwards, 20 I. & N. Dec. 191, 195-96, 1990 WL 385757 (1990) (citations omitted).12
*1195It bears repeating that over one-half of all applications for waiver under section 1182(c) had been granted in the relevant time period. INS v. St. Cyr, 533 U.S. 289, 121 S.Ct. 2271, 2277 n. 5, 150 L.Ed.2d 347 (2001). The class of persons affected was "extremely large," with relief granted to over 10,000 aliens. Id. at 2277. Thus, as a matter of sheer arithmetic, it seems at first blush that there was certainly a reasonable probability that defendant could have avoided deportation had he been informed of and applied for the waiver for which he was eligible (or would have been eligible in one more day). But of course we cannot overlook the fact that defendant's prior conviction was for a very serious crime, attempted murder. And, we must look also to the other factors set out by the INS as quoted supra.
The district judge found that the seriousness of the prior conviction was the only factor weighing against defendant in this balancing process. As she noted, although that factor is a serious consideration, this form of relief was available for convicted felons under appropriate circumstances. She found that there were a number of factors that would have weighed in his favor. These included the fact that both of his parents were legal permanent residents of the United States (they have since become citizens), that he had lived in the United States since age four, and that he had no other criminal record.
The government contends that the length of defendant's residence should not count in his favor when he was not granted the legal right to residence until 1987, when he was age seventeen or eighteen. We do not think, however, that we can count against defendant the fact that he was in this country without permission, as the government seems to want us to do, considering that he was a child living with his parents. It is not realistic to expect a child to do anything else. And while we recognize the important policy considerations behind the government's argument, which we perceive to be the desire to not condone or encourage violation of the immigration laws, we do not think this actually carries weight in these circumstances. Defendant grew up in this country because his parents were here-legally as far as the record reveals. We think that in consideration of the "social and humane considerations in an alien's favor," Edwards, supra, that would have been relevant to the discretionary waiver decision, had that avenue of relief been pursued, this would have weighed in his favor. He was 25 years old at the time of the deportation proceeding and had not lived in Mexico since the age of four. His parents, to whom he could naturally have been expected to turn for assistance on his re-entry into society after his imprisonment, were permanent residents of this country. We believe that the district court was correct in citing the length of defendant's residence in the United States as a factor that would have weighed in his favor, in light of the fact that the INS would have been obligated to look at social and humane considerations, not only legalities, in its deliberations.
The consideration of defendant's conviction in the balancing of equities bears further comment. Section 212(c) presupposes that a criminal conviction for an aggravated felony has occurred. Therefore, the fact of conviction is not the *1196pertinent consideration. Congress could have decided to deny discretionary relief to all persons convicted of a serious crime, but it explicitly chose not to do so. Thus, the immigration judge must consider each defendant’s case individually, looking at the underlying circumstances of the conviction rather than the conviction itself. See, e.g., Yepes-Prado, 10 F.3d at 1371; see also Martinez-Benitez v. INS, 956 F.2d 1053, 1055 (11th Cir.1992). In this case, the record reveals that while defendant was convicted of attempted murder,, the incident occurred when he was with a group of five young men, he did not wield a weapon and was not the principal perpetrator, and he was twenty years old at the time. Rec., vol. 1, doc. 35, attach. 1 (state court indictment); Aplt.App. at 87 (trans., appeal from detention order). In assessing whether defendant might have been successful in applying for waiver, we must look at whether the act of which he was convicted was “so grave that, despite the outstanding equities that favor the grant of discretionary relief, he must be deported.” Yepes-Prado, 10 F.3d at 1373. It is certainly arguable that is not the case here.13
We conclude that there was a reasonable probability that defendant would have been granted a waiver but for the failure to explain to him the nature of that relief. We are persuaded to agree with the district judge’s conclusion that “[u]pon review of the favorable and unfavorable considerations in Defendant’s case, the Court believes that a 212(c) waiver would have been granted had Defendant applied for one at the time of his deportation proceedings.” Memorandum Opinion and Order at 11, ApltApp. at 174. Therefore, we hold that he did suffer prejudice from the procedural defects in the 1994 deportation proceeding.
E
Finally, defendant must show that the fundamental unfairness in the deportation proceeding deprived him of judicial review. E.g., Meraz-Valeta, 26 F.3d at 998. We do not think that this point requires further explication. The same reasoning that supports our conclusion supra that the collateral attack is not barred by the failure to exhaust administrative remedies also leads to the conclusion that defendant was deprived of judicial review. The failure to inform him of the relief available to him and of the legal assistance available to him to pursue that relief violated his right of due process. And that violation, by failing to inform him of any ground for challenge, deprived him of the judicial review. See United States v. Mendoza-Lopez, 481 U.S. 828, 839-40, 107 S.Ct. 2148, 95 L.Ed.2d 772 (1987) (due process violations in deportation proceedings completely deprived aliens of right of judicial review where IJ permitted waivers of the right to appeal “that were not the result of considered judgments ... and failed to advise [aliens] properly of their eligibility to apply for suspension of deportation”).
Conclusion
We hold that the district court correctly decided that Defendant Aguirre was deprived of his due process rights in the 1994 deportation proceeding and suffered prejudice as a result. The district judge gave her -ruling with this moving conclusion: *1197Following his release from imprisonment, Defendant had only one chance to fight for his right to remain in the United States as a legal permanent resident. However, due to the IJ’s failure to adequately satisfy his obligations at the deportation proceeding, Defendant did not have the tools with which he could have made that fight. As a consequence, Defendant could not have made a “considered and intelligent” waiver of his appeal rights, and the Court has no choice but to declare the prior deportation, upon which the current indictment is based, to be unconstitutional.
Memorandum Opinion and Order at 14, ApliApp. at 177.
We are convinced of the justness of her conclusion and accordingly her decision is
AFFIRMED.
. See note 3, infra.
. The hearing had been taped but not transcribed at the time. The transcription was done by a New Mexico court reporting service from the tape, probably around the time of the district court hearing, although the date of transcription unfortunately is not provided. The reporter's certificate says that the tape was of "poor” quality. Aplt.App. at 68.
. If he had actually served more than five years, he would not have been eligible for the waiver of deportation that is discussed extensively in this opinion. The government has not asserted, either on appeal or in the district court, that Aguirre could not have received the waiver on this basis, however, likely because Aguirre had included in the 63 months about six months when he had been in pretrial detention. Aplt.App. at 131; see also Memorandum and Order at 5, n.3, Aplt. App. at 168. In any event, we will not consid*1186er this issue because it has not been advanced by the government.
. While hearing argument of counsel after the evidentiary portion of the hearing on the motion to dismiss, the district judge commented that she had never heard of the section 212(c) waiver until this case arose. The judge told the prosecutor, "I, as a matter of fact, was going to ask you to tell me what the significance of the 'one more day' matter meant.” The prosecutor said, "Your honor, ... I don't know either.” Aplt.App. at 150.
. There is a conflict in the record on this point. The transcript of the deportation hearing recites a statement by the IJ to the group of aliens before him that “You each have a list of free legal services.” Aplt.App. at 7-8. There was no contradiction of this statement at that hearing. However at the hearing on Defendant's motion to dismiss the indictment, in his sworn testimony Defendant Aguirre denied that he was given such a list. Id. at 116-17.
.The dissent says it would hold that the district court’s finding that Aguirre was not given a list of free legal services was clearly erroneous. This foundation for the dissent is suggested despite the fact of a clear conflict in the testimony before the district judge in the hearing on the motion to dismiss. Aguirre *1188took the stand and during his testimony was asked whether he was "personally provided by the IJ a list of free legal services or organizations that could have advised you in that proceeding?" Aguirre answered “No, I was not.” He was then asked if he was ever advised by the IJ personally that he had bond in his case, and again Aguirre testified "No, I was not.” Aplt.App. 116-17.
There was a conflict in the record in that the IJ stated to the group of 20 aliens before him that "You each have a list of free legal services! ]" and there was no contradiction at that hearing of the judge’s statement. The trial judge resolved this conflict by accepting Aguirre's position as a fact "that Defendant did not receive a list of free legal services and was not advised of his eligibility for bond....”
The dissent suggests that we hold that the district court’s findings that Aguirre was not given a list of free legal services was clearly erroneous. This suggestion runs counter to the emphatic opinion of Justice White in Anderson v. City of Bessemer City, 470 U.S. 564, 105 S.Ct. 1504, 84 L.Ed.2d 518 (1985). He there stated:
If the district court's account of the evidence is plausible in light of the record viewed in its entirety, the Court of Appeals may not reverse it even though convinced that had it been sitting as a trier of fact, it would have weighed the evidence differently. Where there are two permissible views of the evidence, the factfinder's choice between them cannot be clearly erroneous.
Id. at 573-74, 105 S.Ct. 1504 (emphasis added). See also United States v. De la Cruz-Tapia, 162 F.3d 1275, 1277 (10th Cir.1998); United States v. Toro-Pelaez, 107 F.3d 819, 824-25 (10th Cir. 1997).
. The dissent argues at page 4 that it defies common sense to believe that the Immigration Judge's use of the word ''pardon” as opposed to "waiver” would have made any difference to Aguirre-Tello. We do not focus on the legal technicalities that Aguirre-Tello was confronted with.
Our concern is that the IJ’s inadequate explanation actually misled Aguirre-Tello as noted by the trial judge. She pointed out that a pardon "is commonly understood to be a rare act of forgiveness by an executive authority. See, e.g. Black's Law Dictionary, 1113 (6th ed.1990).” Memorandum Opinion and Order at 7, Aplt.App. at 170 (emphasis added). On the other hand, relief by a waiver under § 212(c) was granted to over 10,000 aliens between 1989 and 1995 alone — some 51.5% of the applications for such relief for which a final decision was reached. INS v. St. Cyr, 533 U.S. 289, 121 S.Ct. 2271, 2277 & n. 5, 150 L.Ed.2d 347 (2001) citing Julie K. Rannick, The Anti-Terrorism and Effective Death Penalty Act of 1996: A Death Sentence for the 212(c) Waiver, 28 U. MIAMI INTER-AM. L. REV. 123, 137 n.80 (1996), referring to statistics published as CHART: EXECUTIVE OFFICE OF IMMIGRATION REVIEW STATISTICS FOR ALL IMMIGRATION JUDGES). Thus, although a waiver of deportation is a matter of grace like a pardon, the fact remains that during the relevant time period, the Attorney General was bestowing this grace on over half of those who applied.
And we are not persuaded by the dissent's argument that in any event, Aguirre "knowingly and with full understanding of his situation expressed his desire to return immediately to Mexico rather than remain for even a day to try to avoid deportation.” The telling points about Aguirre's situation are that he was never given an explanation of the waiver remedy, nor of the legal services he might obtain to pursue frequently granted waiver relief. Not having such information, his choices cannot fairly be said to have been knowing and with full understanding of his situation.
. The dissent argues in its Part II, p. 9 et seq., that Aguirre "... had no constitutional right to be advised of the possibility of such a waiver, and the I.J.’s failure to so advise him did not render his deportation proceeding fundamentally unfair.” That position was not asserted by the government's brief. See Aplt.’s Brief in Chief, at 17 et seq. In that proposition the government developed its arguments on its central contention that "the district court erred in holding that Aguirre's deportation hearing was fundamentally unfair.” However the government did not dispute the requirement that Aguirre be advised of his right to seek waiver of deportation, recognized in the government's own regulations (8 C.F.R. § 242.17 (1994)).
. The regulations requiring the Immigration Judge to inform Aguirre of his apparent eligibility for relief in 1994 are found in 8 C.F.R. § 242.17. The regulations clearly provided that the “immigration judge shall inform the defendant of his or her apparent eligibility to apply for any of the benefits enumerated in this paragraph...." Id. § 242.17(a). In that paragraph the regulation specifically provides that an "application for asylum or withholding of deportation must be filed with the Office of the Immigration Judge....” 8 C.F.R. § 242.17(c)(3). In United States ex rel. Accardi v. Shaughnessy, 347 U.S. 260, 268, 74 S.Ct. 499, 98 L.Ed. 681 (1954), the Court recognized that immigration regulations there required an exercise of discretion and while an applicant may fail to convince the board or the Attorney General that he is entitled to suspension, the exercise of their discretion will at least have "... afforded that due process required by the regulations in such proceedings-" See also Weathers v. West Yuma County School District, 530 F.2d 1335, 1338 (10th Cir.1976). That an exercise of discretion is constitutionally required implies that the applicant must be informed of that potential relief. Indeed, Mendoza-Lopez expressly requires that the judge “explain adequately [the alien's] right to suspension of deportation ...” according to the regulations the government has established. Mendoza-Lopez, 481 U.S. at 839-40, 107 S.Ct. 2148.
Thus in light of the recognition of the applicant’s right to be afforded notice about waivers of deportation provided in the regulations, and Accardi s recognition of due process mandating the notice the regulation required, the dissent is in error in saying that the majority opinion creates new constitutional rights.
. The government does not dispute that the IJ had a duty, under INS regulations, to advise of the availability of discretionary relief.
. In its brief, the government argues that defendant could not show prejudice because pursuant to 8 U.S.C. § 1228(c) (2000), an alien convicted of an aggravated felony is conclusively presumed to be deportable. That provision was added in 1996, however, and has no bearing on our inquiry into the relief that might have been available to defendant in 1994. The government has not shown that the district court erred by inquiring into whether relief would have been available under 8 U.S.C. § 1182(c) (1994). Cf. United States v. Muro-Inclan, 249 F.3d 1180, 1184 (9th Cir.2001) (distinguishing case where relief was potentially available under subsection (h) from one under subsection (c)).
. The government argues for the "extraordinary hardship” standard of 8 U.S.C. § 1182(h)(1)(B). We conclude, however, that standard applies only to waivers under that subsection, not to waivers under subsection (c), with which we are concerned here.
The cases cited by the dissent recite "extraordinary hardship” as a requirement for relief under section 212(c) but either cite no *1195authority or cite authority that reveals a history in which that one factor was given as an example taken from the long list of other relevant factors. Thus, by mere careless citation, without discussion or holdings to that effect, "extraordinary hardship" began to be listed as a requirement. Consequently, the Second, Third, and Seventh Circuit cases cited by the dissent are unpersuasive on this point.
. As to the issue of rehabilitation, we also note that it is a factor to be taken into consideration but is not a prerequisite, particularly where circumstances do not permit the defendant to make any viable showing on the point, for example, as in this case, where the deportation proceeding follows immediately after release from prison. See, e.g., Yepes-Prado, 10 F.3d at 1373.