Plaintiffs represent a class of legal aliens who will lose their Medicaid benefits when last year’s Colorado Senate Bill OS-176 (SB 03-176) takes effect. They contend that the eligibility requirements of SB 03-176 violate the Equal Protection Clause of the Fourteenth Amendment to the United States Constitution, and that the state’s procedures for terminating benefits violate Medicaid law and the Due Process Clause of the Fourteenth Amendment. The district court denied Plaintiffs’ motion for a preliminary injunction against implementation of SB 03-176. We granted an injunction pending resolution of this appeal. We now reject Plaintiffs’ contentions except that we agree that the state’s procedures violate the Medicaid Act in denying some members of the class a right to a hearing. Accordingly, we vacate our injunction, and we affirm in part and reverse in part the district court’s denial of a preliminary injunction.
I. BACKGROUND
A. Medicaid
Prior to the enactment of SB 03-176, which was signed into law on March 5, 2003, and scheduled to take effect on April 1, 2003, Colorado provided optional Medicaid coverage to all legal aliens eligible under federal law to receive such coverage. The new statute would repeal optional Medicaid coverage, terminating Medicaid benefits to approximately 3,500 aliens residing in Colorado.
Medicaid is a joint state and federal medical assistance program for the poor, disabled, and others in need. 42 U.S.C. § 1396 et seq. It provides coverage for such medical services as inpatient and outpatient hospital care, physicians’ services, prescriptions, home health care services, and nursing home care. Id. §§ 1396a(a)(10)(A), 1396d(a)(l)-(5), (17) & (20). Although states are not required to participate in Medicaid, if a state does elect to participate, it must comply with the minimum requirements of the federal Medicaid Act in order to receive federal matching funds. See Wilder v. Va. Hosp. Ass’n, 496 U.S. 498, 502, 110 S.Ct. 2510, 110 L.Ed.2d 455 (1990). States implement their Medicaid programs in accordance with comprehensive written plans that must be submitted to and approved by the Secretary of the United States Department of Health and Human Services. See 42 U.S.C. § 1396. Colorado has opted to participate in the Medicaid program, and has designated the Department of Health Care Policy and Financing (the Colorado Department), currently headed by Defendant Karen Reinertson (sued here in her official capacity), as the single state agency responsible for administering Medicaid. See Colo.Rev.Stat. § 26-4-104(1).
Federal law requires participating states to provide full Medicaid services to all individuals designated as categorically *1245needy. 42 U.S.C. § 1396a(a)(10)(A)(i). States have discretion to provide full Medicaid coverage to additional “optional” segments of the population. Id. § 1396a(a)(10)(A)(ii). Emergency care must be provided to all individuals in need of such services. 8 U.S.C. § 1611(b)(1)(A).
In 1996 Medicaid law changed significantly. The federal Personal Responsibility and Work Opportunity Reconciliation Act of 1996 (PRWORA), Pub.L. No. 104-193, 110 Stat. 2105 (1996) (often referred to as the Welfare Reform Act), was enacted. Explaining the purpose of the provisions with respect to aliens, the Act states:
The Congress makes the following statements concerning national policy with respect to welfare and immigration:
(1) Self-sufficiency has been a basic principle of United States immigration law since this country’s earliest immigration statutes.
(2) It continues to be the immigration policy of the United States that — •
(A) aliens within the Nation’s borders not depend on public resources to meet their needs, but rather rely on their own capabilities and the resources of their families, their sponsors, and private organizations, and
(B) the availability of public benefits not constitute an incentive for immigration to the United States.
(3) Despite the principle of self-sufficiency, aliens have been applying for and receiving public benefits from Federal, State, and local governments at increasing rates.
(4) Current eligibility rules for public assistance and unenforceable financial support agreements have proved wholly incapable of assuring that individual aliens not burden the public benefits system.
(5) It is a compelling government interest to enact new rules for eligibility and sponsorship agreements in order to assure that aliens be self-reliant in accordance with national immigration policy.
(6) It is a compelling government interest to remove the incentive for illegal immigration provided by the availability of public benefits.
(7) With respect to the State authority to make determinations concerning the eligibility of qualified aliens for public benefits in this chapter, a State that chooses to follow the Federal classification in determining the eligibility of such aliens for public assistance shall be considered to have chosen the least restrictive means available for achieving the compelling governmental interest of assuring that aliens be self-reliant in accordance with national immigration policy.
8 U.S.C. § 1601QM7).
The PRWORA imposes several limitations on the availability of Medicaid benefits to aliens. 8 U.S.C. § 1601 et seq; id. § 1612(b)(3)(C). Prior to the PRWORA, Medicaid benefits were mandated for otherwise qualified aliens who were lawfully admitted for permanent residence or otherwise permanently residing in the United States. See 42 C.F.R. § 435.406(a) (1990). Now, the PRWORA requires states to provide Medicaid coverage only to “qualified aliens,” which it defines as lawful permanent residents, refugees, aliens granted asylum, and certain other specified categories of lawfully present aliens. 8 U.S.C. § 1612(b); id. § 1641(b). The PRWORA also provides that most of these qualified aliens are ineligible for Medicaid benefits until they have lived in the United States for at least five years. Id. § 1613. But the five-year requirement does not apply to certain qualified aliens, such as lawful permanent residents who have worked in the United States for 40 qualifying quarters, veterans, and active-duty members of the military. Id. § 1612(b)(2). Nor does *1246the requirement apply to qualified aliens who entered the United States prior to August 22,1996. Id. § 1613(a).
The PRWORA does, however, allow states to provide optional Medicaid coverage to legal aliens not included within Congress’s definition of “qualified aliens.” Id. § 1612(b). In essence, states may redefine “qualified aliens” to cover additional legal aliens, so long as they do not cover those aliens explicitly excluded by the PRWORA (e.g., most aliens who have not lived in the United States for five years). Id.
Initially Colorado opted to provide coverage beyond that mandated by the PRWORA. In 1997 Colorado responded to the PRWORA by enacting legislation that maintained the optional Medicaid coverage it had previously provided to all lawfully present aliens who were otherwise eligible. See 1997 Colo. Sess. Laws 1257-58. But Colorado policy changed in March of 2003. Faced with an enormous budget shortfall, the state looked to its Medicaid program for savings. The Colorado legislature passed and the governor signed SB 03-176, which removed the optional Medicaid coverage Colorado had been providing to legal aliens. SB 03-176 § 1. After SB 03-176 takes effect, only those aliens that Congress defined in the PRWORA as “qualified aliens” will be eligible for Medicaid in Colorado. SB 03-176 § 2; Colo. Rev.Stat. § 26-4-201(2)(a)-(b). The state estimates that it will save $5.9 million annually by eliminating optional alien coverage.
B. Coverage Termination Procedures
In Colorado the county departments of social services make the initial Medicaid eligibility determinations. Colo.Rev.Stat. § 26-4-106(l)(a). Accordingly, in anticipation of enactment of SB 03-176, the Colorado Department notified the state’s 64 counties of the impending Medicaid eligibility changes and instructed them on procedures to use in effectuating those changes.
First, the Department sent the counties two letters, informing them that SB OS-176 was moving through the legislative process and that the Department would keep them informed as the legislation progressed. Then, after the legislation was passed by the legislature but before it was signed by the Governor, the Department sent a third, more-detailed letter. The letter, labeled HCFP 03-001, set forth an eligibility redetermination process providing for county officials to ascertain whether individuals whose Medicaid eligibility was eliminated by SB 03-176 could qualify under a different eligibility category.
Five days after the HCFP 03-001 letter was sent to the counties, a statewide conference call was conducted to discuss the letter. Forty counties participated in the conference call. Once the governor signed the bill, the Colorado Department notified the counties and instructed them to provide notice to affected recipients. The counties were directed to provide at least 10 days’ notice prior to termination of benefits for all individuals losing coverage as a result of SB 03-176.
C. Procedural History
On March 27, 2003, Plaintiffs filed this class-action lawsuit to enjoin the implementation of SB 03-176. Class members include legal aliens who rely on Medicaid to cover important medical services, including chemotherapy, nursing home care, home health care, surgical care, and life-sustaining prescription drug coverage. Without Medicaid, Plaintiffs claim, they will be unable to afford these necessary services and will suffer serious injuries and irreparable harm. Plaintiffs contend that in some cases the loss of medical care could be life threatening.
*1247Plaintiffs’ suit seeks a judgment declaring that SB 03-176’s eligibility requirements violate the Equal Protection Clause of the Fourteenth Amendment because they discriminate against legal aliens, and that Defendant’s procedures for terminating benefits are inadequate under Medicaid law and the Due Process Clause of the Fourteenth Amendment. Plaintiffs also seek an injunction permanently enjoining termination of benefits under SB 03-176.
The district court granted Plaintiffs’ request for a temporary restraining order, but it later denied their motion for a preliminary injunction and lifted the temporary restraining order. Plaintiffs then moved this court for an injunction pending appeal. We granted that motion and expedited the appeal. See Soskin v. Reinertson, No. 03-1162 (10th Cir. Apr. 25, 2003) (order granting injunction pending appeal). After oral argument we notified the Attorney General of the United States, in accordance with Fed. R.App. P. 44, that this case called into question the constitutionality of an Act of Congress, 8 U.S.C. § 1612(b) (which authorizes states to reduce Medicaid coverage to aliens). The United States filed a brief in support of the constitutionality of the statute.
II. DISCUSSION
We have jurisdiction under 28 U.S.C. § 1292. We
review[ ] a district court’s grant or denial of a preliminary injunction for an abuse of discretion. A district court abuses its discretion where it commits a legal error or relies on clearly erroneous factual findings, or where there is no rational basis in the evidence for its ruling. We examine the district court’s underlying factual findings for clear error, and its legal determinations de novo.
Davis v. Mineta, 302 F.3d 1104, 1110-11 (10th Cir.2002) (internal citations and quotation marks omitted). For Plaintiffs to be entitled to a preliminary injunction, they must show:
(1) a substantial likelihood of prevailing on the merits; (2) irreparable harm unless the injunction is issued; (3) [that] the threatened injury outweighs the harm that the preliminary injunction may cause the opposing party; and (4) [that] the injunction, if issued, will not adversely affect the public interest. If [Plaintiffs] can establish that the latter three requirements tip strongly in [their] favor, the test is modified, and [Plaintiffs] may meet the requirement for showing success on the merits by showing that questions going to the merits are so serious, substantial, difficult, and doubtful as to make the issue ripe for litigation and deserving of more deliberate investigation.
Id. at 1111 (internal citations and quotation marks omitted).
A. Equal Protection Claim
The Fourteenth Amendment to the United States Constitution declares that “[n]o State shall ... deny to any person within its jurisdiction the equal protection of the laws.” The Equal Protection Clause “keeps governmental decision makers from treating differently persons who are in all relevant respects alike.” Nordlinger v. Hahn, 505 U.S. 1, 10, 112 S.Ct. 2326, 120 L.Ed.2d 1 (1992). Plaintiffs allege that SB 03-176 violates the Equal Protection Clause because it improperly discriminates between citizens and legal aliens. They argue that such discrimination is subject to strict scrutiny, so the statute can be upheld only if it “advanee[s] a compelling state interest by the least restrictive means available.” Bernal v. Fainter, 467 U.S. 216, 219, 104 S.Ct. 2312, 81 L.Ed.2d 175 (1984).
*1248Defendant disputes that strict scrutiny is the appropriate standard for reviewing the statute. She contends that Congress used its plenary immigration powers to enact the PRWORA, and because Colorado was acting in accordance with the PRWORA when it enacted SB 03-176, the more deferential rational-basis test applies. The statute satisfies that test, she argues, because it is rationally related to a legitimate state interest. See Cleburne v. Cleburne Living Ctr., 473 U.S. 432, 440, 105 S.Ct. 3249, 87 L.Ed.2d 313 (1985) (under rational-basis standard of review, “legislation is presumed to be valid and will be sustained if the classification drawn by the statute is rationally related to a legitimate state interest.”).
The parties appear to agree that SB OS-176 would not survive strict scrutiny but would satisfy the rational-basis test. Thus, the constitutionality of SB 03-176 depends on the level of scrutiny to which the law is subject. We turn to Supreme Court precedent for guidance.
1. Graham v. Richardson
Plaintiffs rely heavily on Graham v. Richardson, 403 U.S. 365, 91 S.Ct. 1848, 29 L.Ed.2d 534 (1971), which resolved a consolidated appeal involving two cases arising out of different statutory schemes: one from Arizona and one from Pennsylvania. Id. at 366-70, 91 S.Ct. 1848. The Arizona statute limited alien eligibility for benefits under federally funded programs for persons who were disabled, in need of old-age assistance, or blind. Id. at 367, 91 S.Ct. 1848. The state limitation on eligibility for the programs provided: “No person shall be entitled to general assistance who does not meet and maintain the following requirements: 1. Is a citizen of the United States, or has resided in the United States a total of fifteen years.” Id. (internal quotation marks omitted). The Pennsylvania statute concerned a welfare program that was not federally funded. It limited state benefits to those Pennsylvania residents who either were citizens of the United States or had filed a declaration of intention to become a citizen. Id. at 368, 91 S.Ct. 1848.
The Court observed that “the Arizona and Pennsylvania statutes in question create two classes of needy persons, indistinguishable except with respect to whether they are or are not citizens of this country.” Id. at 371, 91 S.Ct. 1848. Regarding the Arizona statute, the Court wrote that “[otherwise qualified United States citizens living in Arizona are entitled to federally funded categorical assistance benefits without regard to length of national residency, but aliens must have lived in this country for 15 years in order to qualify for aid.” Id. As for Pennsylvania, the Court said, “United States citizens living in Pennsylvania, unable to meet the requirements for federally funded benefits, may be eligible for state-supported general assistance, but resident aliens as a class are precluded from that assistance.” Id.
The Court first rejected the states’ argument that they could favor United States citizens over aliens in the distribution of welfare benefits. While the Court recognized that “[u]nder traditional equal protection principles, a State retains broad discretion to classify so long as its classification has a reasonable basis,” id., it was well established “that classifications based on alienage, like those based on nationality or race, are inherently suspect and subject to close judicial scrutiny.” Id. at 372, 91 S.Ct. 1848 (footnotes omitted). “Aliens as a class,” the Court wrote, “are a prime example of a discrete and insular minority for whom such heightened judicial solicitude is appropriate.” Id. (internal quotation marks and citation omitted).
The Court then concluded that the Arizona and Pennsylvania laws could not withstand strict scrutiny. Id. at 376, 91 *1249S.Ct. 1848. It rejected the states’ fiscal motive: “[J]ustification of limiting expenses is particularly inappropriate and unreasonable when the discriminated class consists of aliens. Aliens like citizens pay taxes and may be called into the armed forces.... [Ajliens may live within a state for many years, work in the state and contribute to the economic growth of the state.” Id. (internal quotation marks omitted). Thus, the Court concluded, “a state statute that denies welfare benefits to resident aliens and one that denies them to aliens who have not resided in the United States for a specified number of years violate the Equal Protection Clause.” Id.
In addition, and significantly for present purposes, the Court rejected Arizona’s argument that its durational residency requirement for aliens was authorized by a federal statute. Id. at 380-82, 91 S.Ct. 1848. The statute, 42 U.S.C. § 1352(b) (1971), stated: “The Secretary shall approve any plan which fulfills the conditions specified in subsection (a) of this section, except that he shall not approve any plan which imposes, as a condition of eligibility for aid to the permanently and totally disabled under the plan — ... (2) Any citizenship requirement which excludes any citizen of the United States.” Id. at 380, 91 S.Ct. 1848 (internal quotation marks omitted). Arizona argued that the statutory language implicitly authorized citizenship requirements that excluded non-citizens.
The Court observed that “[o]n its face, the statute does not affirmatively authorize, much less command, the States to adopt durational residency requirements or other eligibility restrictions applicable to aliens.” Id. at 381, 91 S.Ct. 1848. It then traced the language in question to the Social Security Act of 1935, when the language apparently was included to prevent treating naturalized citizens differently from native-born citizens. Id. at 381, 91 S.Ct. 1848. The Court noted that the statute may have reflected Congressional understanding of the law as it stood in 1935, before Takahashi v. Fish & Game Comm’n, 334 U.S. 410, 68 S.Ct. 1138, 92 L.Ed. 1478 (1948), had established the equal-protection rights of aliens. Graham, 403 U.S. at 382, 91 S.Ct; 1848. Now, however, significant constitutional concerns would' be raised by discrimination against aliéns. The Court wrote:
[WJere [the federal statute] to be read so as to authorize discriminatory treatment of aliens at the option of the States, Takahashi demonstrates that serious constitutional questions are presented. Although the Federal Government admittedly has broad constitutional power to determine what aliens shall be admitted to the United States, the period they may remain, and the terms and conditions of their naturalization, Congress does not have the power to authorize the individual States to violate the Equal Protection Clause.
Id. Moreover, the Court said that “[u]nder Art. I, § 8, cl. 4, of the Constitution, Congress’ power is to ‘establish an uniform Rule of Naturalization,’ ” id. (emphasis added), and that a “congressional enacfi ment construed so as to permit state legislatures to adopt divergent laws on the subject of citizenship requirements for federally supported welfare programs would appear to contravene this explicit constitutional requirement of uniformity.” Id. These constitutional concerns, the Court declared, argued against interpreting the statutory language to authorize state discrimination against aliens. . “Since statutes should be construed whenever possible so as to uphold their constitutionality, we conclude that [the statute] does not authorize the Arizona 15-year national residency requirement.” Id. at 382-83, 91 S.Ct. 1848 (internal quotation marks and citation omitted).
*1250A footnote to the quoted passage noted that the Court had “no occasion to decide whether Congress, in the exercise of the immigration and naturalization power, could itself enact a statute imposing on aliens a uniform nationwide residency requirement as a condition of federally funded welfare benefits.” Id. at 382 n. 14, 91 S.Ct. 1848. As we will discuss below, that issue was resolved in Mathews v. Diaz, 426 U.S. 67, 96 S.Ct. 1883, 48 L.Ed.2d 478 (1976).
In the years immediately following Graham, the Supreme Court reemphasized the central holding of the case: that state laws creating citizen-alien classifications must meet strict scrutiny. See, e.g., Bernal, 467 U.S. at 219-20, 104 S.Ct. 2312 (citizenship requirement for state notaries public is subject to strict scrutiny); Examining Bd. v. Flores de Otero, 426 U.S. 572, 601-02, 96 S.Ct. 2264, 49 L.Ed.2d 65 (1976) (same for state civil engineering licenses); In re Griffiths, 413 U.S. 717, 721, 93 S.Ct. 2851, 37 L.Ed.2d 910 (1973) (same for admission to state bar); Sugarman v. Dougall, 413 U.S. 634, 642, 93 S.Ct. 2842, 37 L.Ed.2d 853 (1973) (same for state civil service jobs). In particular, in Nyquist v. Mauclet, 432 U.S. 1, 97 S.Ct. 2120, 53 L.Ed.2d 63 (1977), the Court held that a state could not circumvent Graham by contending that it was merely distinguishing among aliens, as opposed to discriminating against aliens vis-a-vis citizens. Reviewing a statute restricting certain aliens’ access to state-funded tuition assistance, the Court rejected the state’s argument that strict scrutiny should not apply because the classification “distinguishe[d] only within the heterogeneous class of aliens and d[id] not distinguish between citizens and aliens vel non.” Id. at 8, 97 S.Ct. 2120 (internal quotation marks omitted). The Court wrote:
Graham v. Richardson ... undermines [the state’s] position. In that ease, the Court considered an Arizona statute that imposed a durational residency requirement for welfare benefits on aliens but not on citizens. Like the New York statute challenged here, the Arizona statute served to discriminate only within the class of aliens: Aliens who met the durational residency requirement were entitled to welfare benefits. The Court nonetheless subjected the statute to strict scrutiny and held it unconstitutional. The important points are that [the tuition assistance restriction] is directed at aliens and that only aliens are harmed by it. The fact that the statute is not an absolute bar does not mean that it does not discriminate against the class.
Id. at 8-9, 97 S.Ct. 2120.
2. Mathews v. Diaz
In Mathews v. Diaz, 426 U.S. 67, 96 S.Ct. 1883, 48 L.Ed.2d 478 (1976), the Court answered the question left open in Graham, holding that the federal government could impose a uniform residency requirement as a condition of receiving federal benefits. Mathews considered a federal law granting Medicare benefits to certain resident citizens 65 years of age and older, but denying eligibility to comparable aliens unless they had been admitted for permanent residence and had resided in the United States for at least five years. Id. at 70, 96 S.Ct. 1883.
The Court explained why Congress’s broad constitutional powers over naturalization and immigration give it authority to treat aliens differently from citizens:
The fact that all persons, aliens and citizens alike, are protected by the Due Process Clause does not lead to the further conclusion that all aliens are entitled to enjoy all the advantages of citizenship or, indeed, to the conclusion that all aliens must be placed in a single homogeneous legal classification. For a *1251host of constitutional and statutory provisions rest on the premise that a legitimate distinction beüueen citizens and aliens may justify attributes and benefits for one class not accorded to the other; and the class of aliens is itself a heterogeneous multitude of persons with a wide-ranging variety of ties to this country.
In the exercise of its broad power over naturalization and immigration, Congress regularly makes rules that would be unacceptable if applied to citizens. The exclusion of aliens and the reservation of the power to deport have no permissible counterpart in the Federal Government’s power to regulate the conduct of its own citizenry. The fact that an Act of Congress treats aliens differently from citizens does not in itself imply that such disparate treatment is “invidious.”
In particular, the fact that Congress has provided some welfare benefits for citizens does not require it to provide like benefits for all aliens. ...
For reasons long recognized as valid, the responsibility for regulating the relationship between the United States and our alien visitors has been committed to the political branches of the Federal Government. Since decisions in these matters may implicate our relations with foreign powers, and since a wide variety of classifications must be defined in the light of changing political and economic circumstances, such decisions are frequently of a character more appropriate to either the Legislature or the Executive than to the Judiciary. ...
... In short, it is unquestionably reasonable for• Congress to make an alien’s eligibility depend on both the character and the duration of his residence. Since neither requirement is wholly irrational, this case essentially involves nothing more than a claim that it would have been more reasonable for Congress to select somewhat different requirements of the same kind.
Id. at 78-83, 96 S.Ct. 1883 (footnotes omitted) (emphasis added).
Matheius also distinguished Graham, recognizing that its “equal protection analysis ... involves significantly different considerations because it concerns the relationship between aliens and the States rather than between aliens and the Federal Government.” Id. at 84-85, 96 S.Ct. 1883. It explained that
[ijnsofar as state welfare policy is concerned, there is little, if any, basis for treating persons who are citizens of another State differently from persons who are citizens of another country. Both groups are noncitizens as far as the State’s interests in administering its welfare programs are concerned. Thus, a division by a State of the category of persons who are not citizens of that State into subcategories of United States citizens and aliens has no apparent justification, whereas, a comparable classification by the Federal Government is a routine and normally legitimate part of its business.
Id. at 85, 96 S.Ct. 1883.
3. Lower Courts
Neither Graham nor Mathews determines the result in this case. Unlike Graham, here we have specific Congressional authorization for the state’s action, the PRWORA. Unlike Mathews, here we have a state-administered program, and the potential for states to adopt coverage restrictions with respect to aliens that are not mandated by federal law.
The fact of state administration in itself is not a distinction from Mathews that has impressed the circuits that have addressed the matter. Following Mathews, several circuits have applied rational-basis review *1252to uphold federal statutes restricting state-administered welfare benefits to legal aliens. See, e.g., Lewis v. Thompson, 252 F.3d 567, 582 (2d Cir.2001) (upholding under rational-basis review PRWORA restrictions on alien eligibility for state-administered pre-natal Medicaid benefits); City of Chicago v. Shalala, 189 F.3d 598, 603-05 (7th Cir.1999) (same for supplemental security income (SSI) and food stamps); Aleman v. Glickman, 217 F.3d 1191, 1197 (9th Cir.2000) (same for food stamps); Rodriguez v. United States, 169 F.3d 1342, 1346-50 (11th Cir.1999) (same for SSI and food stamps).
The potential for states to adopt coverage restrictions for aliens that are not federally mandated is, however, more problematic. The difficulty is illustrated by opinions addressing non-mandated state restrictions — one each from the high courts of New York and Massachusetts. We discuss each in turn.
In Aliessa v. Novello, 96 N.Y.2d 418, 730 N.Y.S.2d 1, 754 N.E.2d 1085 (2001), the New York Court of Appeals reviewed state alien classifications that were authorized by the PRWORA. Relying on Graham, it concluded that the classification scheme must be subjected to strict scrutiny. New York’s Medicaid system had two components — one was funded jointly by the state and federal governments, and one was solely state-funded. Id., 730 N.Y.S.2d 1, 754 N.E.2d at 1089. Aliessa reviewed only the state-funded portion of the program. Id., 730 N.Y.S.2d 1, 754 N.E.2d at 1089, n. 3.
As it does with regard to jointly funded Medicaid programs, the PRWORA gives states flexibility to grant or deny aliens state-only Medicaid, so long as they adhere to certain requirements. Id., 730 N.Y.S.2d 1, 754 N.E.2d at 1091. In response to the PRWORA, the New York legislature enacted a law that terminated state-only Medicaid coverage for many aliens. Id., 730 N.Y.S.2d 1, 754 N.E.2d at 1091-92. Aliens who lost coverage brought suit, arguing that the new state law violated the state constitution and the Equal Protection Clause of the United States Constitution. Id., 730 N.Y.S.2d 1, 754 N.E.2d at 1092.
The parties’ equal protection arguments in Aliessa mirrored those of the parties in this case: the plaintiffs argued that the state law discriminated based on alienage and that strict scrutiny should apply, and the state argued that it was acting with Congress’s permission and that rational-basis review was appropriate. The court agreed with the plaintiffs, concluding that strict scrutiny applied and that the state law could not withstand it.
The court relied on the language in Graham that “a Federal statute authorizing ‘discriminatory treatment of aliens at the option of the States ’ would present ‘serious constitutional questions,’ ” and that a “congressional enactment construed so as to permit state legislatures to adopt divergent laws on the subject of citizenship requirements for federally supported welfare programs would appear to contravene [the] explicit constitutional requirement of uniformity.” Id., 730 N.Y.S.2d 1, 754 N.E.2d at 1097 (quoting Graham, 403 U.S. at 382, 91 S.Ct. 1848) (emphasis in Alies-sa ). The court reasoned:
[The federal statute] does not impose a uniform immigration rule for States to follow. Indeed, it expressly authorizes States to enact laws extending “any State or local public benefit” even to those aliens not lawfully present within the United States. The converse is also true and exacerbates the lack of uniformity: [the federal statute] provides that, subject to certain exceptions, States are authorized to withhold State Medicaid from even those qualified aliens who are eligible for Federal Medicaid under PRWORA. Thus, in administering their *1253own programs, the States are free to discriminate in either direction — producing not uniformity, but potentially wide variation based on localized or idiosyncratic concepts of largesse, economics and politics. Considering that Congress has conferred upon the States such broad discretionary power to grant or deny aliens State Medicaid, we are unable to conclude that [the federal law] reflects a uniform national policy. If the rule were uniform, each State would carry out the same policy under the mandate of Congress — the only body with authority to set immigration policy.
... New York — along with every other State — with Congressional permission is choosing its own policy with respect to health benefits for resident, indigent legal aliens. Thus, we address this case outside the context of a Congressional command for nationwide uniformity in the scope of Medicaid coverage for indigent aliens as a matter of federal immigration policy.
Id., 730 N.Y.S.2d 1, 754 N.E.2d at 1098 (internal citations omitted). The New York court concluded that strict scrutiny was the appropriate standard by which to assess the New York statute, and held that the statute failed the test. It wrote:
We conclude that [the state law] is subject to ... strict scrutiny, notwithstanding [the federal statute’s] authorization .... [The federal law] is directly in the teeth of Graham insofar as it allows the States to “adopt divergent laws on the subject of citizenship requirements for federally supported welfare programs.” Moreover, [the federal statute] goes significantly beyond what the Graham Court declared constitutionally questionable. In the name of national immigration policy, it impermis-sibly authorizes each State to decide whether to disqualify many otherwise eligible aliens from State Medicaid. [The New York statute] is a product of this authorization. In light of Graham and its progeny, [the federal statute] can give [the New York statute] no special insulation from strict scrutiny review. Thus, [the New York statute] must be evaluated as any other State statute that classifies based on alienage.
Id., 730 N.Y.S.2d 1, 754 N.E.2d at 1098 (footnotes and internal citations omitted); see Kurti v. Maricopa Cty., 201 Ariz. 165, 33 P.3d 499, 505 (App.2001) (applying strict scrutiny to optional coverage of aliens for public health benefits).
The Massachusetts Supreme Judicial Court addressed similar issues in Doe v. Comm’r of Transitional Assistance, 437 Mass. 521, 773 N.E.2d 404 (2002), but reached a different result. It concluded that state-made intra-alien classifications are subject only to rational-basis review. Doe involved a state-only supplemental-benefits program that was enacted to provide coverage to certain aliens who, based on the PRWORA, were going to lose the joint state-federal benefits they had previously received. Id. at 407. But the benefits provided by the supplemental program were restricted to aliens who had resided in Massachusetts for at least six months. Id. at 407-08.
The plaintiffs in Doe argued that the six-month residency requirement violated the Equal Protection Clause because it imposed the requirement on some legal aliens, but not on other legal aliens and citizens. Here again, the dispute hinged on whether strict scrutiny or rational-basis review applied.
The court first emphasized that the benefits provided by the program went only to aliens (not citizens), meaning that the six-month residency requirement did not discriminate between citizens and aliens, but rather only amongst aliens. Then, after reviewing Graham, Mathews, and other *1254relevant law, the court turned to the standard of review:
We conclude that the appropriate standard of review in these circumstances depends on the nature of the classification that creates the distinction between subgroups of aliens. If that classification were a suspect one such as race, gender, or national origin, we would apply a strict scrutiny analysis. Where, as here, that classification is Massachusetts residency, the proper standard of review is rational basis. We reach this conclusion because we find that the operative classification for equal protection purposes in the setting of this case is not alienage, but residency.
Id. at 414 (internal citation omitted). (We note, however, that the court may have applied rational-basis review only because it viewed the distinction between aliens and citizens under the Massachusetts statute as not invidious to aliens. The court wrote:
In concluding that a rational basis standard of review applies, we have also considered the context in which the supplemental program was enacted; its purpose and the clearly noninvidious intent behind its promulgation; the effect of its implementation on mitigating the harm to qualified alien families that might otherwise be without substantial assistance for five years under the requirements of the welfare reform act; and the potential harm to those same families if the Legislature could only choose to create an all-or-nothing program as a remedy to their disqualification from federally funded programs.
Id.)
4. Analysis
The Supreme Court precedents establish two propositions. First, states on their own cannot treat aliens differently from citizens without a compelling justification. See Graham, 403 U.S. at 371-72, 376, 91 S.Ct. 1848. Second, the federal government can treat aliens differently from citizens so long as the difference in treatment has a rational basis. See Mathews, 426 U.S. at 78-83, 96 S.Ct. 1883. This case fits somewhere in between. Plaintiffs claim that its location is clear, because Graham said that “Congress does not have the power to authorize the individual States to violate the Equal Protection Clause.” 403 U.S. at 382, 91 S.Ct. 1848. But we think the issue is more nuanced than the quoted proposition indicates.
We do not read Graham as being as categorical as Plaintiffs claim it is regarding the effect of Congressional authorization of state discrimination against aliens. If the Court had definitively decided that the distinctions made in Arizona law would be unconstitutional regardless of Congressional authorization, there would have been no cause for the Court to examine the legislative history of the federal statute that Arizona relied upon. See Graham, 403 U.S. at 382, 91 S.Ct. 1848. Nor would the Court have needed to rely on a rule of construction — construing the statute to avoid constitutional concerns — to resolve the case before it. See id. As we read Graham, the Court was, in essence, insisting on a clear expression of Congressional intent to permit states to discriminate against aliens before it would tackle the constitutional issue. See id.
We recognize that Graham said that “Congress does not have the power to authorize the individual States to violate the Equal Protection Clause.” Id. But that proposition is almost tautological. The question is not whether Congress can authorize such a constitutional violation. The question is what constitutes such a violation when Congress has (clearly) expressed its will regarding a matter relating to aliens. After all, Congress has extensive powers with respect to aliens derived *1255from specific constitutional provisions as well as from the inherent powers of a sovereign nation. See, e.g., Chae Chan Ping v. United States, 130 U.S. 581, 609, 9 S.Ct. 623, 32 L.Ed. 1068 (1889) (stating that Congress’s immigration power is “an incident of sovereignty”); Harisiades v. Shaughnessy, 342 U.S. 580, 588-89, 72 S.Ct. 512, 96 L.Ed. 586 (1952) (“[A]ny policy toward aliens is vitally and intricately interwoven with contemporaneous policies in regard to the conduct of foreign relations, the war power, and the maintenance of a republican form of government.”).
When Congress exercises these powers to legislate with regard to aliens, the proper standard of judicial review is rational-basis review. That is the lesson of Mathews. Although Mathews involved Medicare, a program administered and funded by the federal government, while the PRWORA involves a program administered and partially funded by the states, that difference, as noted above, is immaterial in assessing the constitutionality of the federal legislation itself. See Lewis, 252 F.3d at 582; City of Chicago, 189 F.3d at 603-05; Aleman, 217 F.3d at 1197; Rodriguez, 169 F.3d at 1346-50.
There is, however, one significant difference between the federal law at issue here and the one at issue in Mathews. The present law gives the states a measure of discretion. Some benefits for aliens are required, some are prohibited. In between, the states are permitted to be more restrictive (or, depending on one’s point of view, more generous). Relying on Graham, one could say, as Plaintiffs do, that when a state elects not to provide aliens with the maximum benefits permitted by federal law, it is discriminating against aliens and the federal government’s imprimatur for such discrimination cannot reduce the level of scrutiny to which the state’s choice is subjected under the Equal Protection Clause. This is the view adopted by the New York Court of Appeals in Aliessa.
We do not share that view. The reason for applying rational-basis review to federal law regarding aliens is that such laws reflect national policy that Congress has the constitutional power to enact. Once Congress has expressed that policy, the courts must be deferential. See Mathews, 426 U.S. at 78-83, 96 S.Ct. 1883. What Plaintiffs fail to consider is that a state’s exercise of discretion can also effectuate national policy. Recall that the PRWORA does not give the states unfettered discretion. Some coverage must be provided to aliens; some coverage is forbidden. State discretion is limited to the remaining optional range of coverage. In exercising that discretion each state is to make its own assessment of whether it can bear the burden of providing any optional coverage. When a state determines that the burden is too high and decides against optional coverage, it is addressing the Congressional concern (not just a parochial state concern) that “individual aliens not burden the public benefits system.” 8 U.S.C. § 1601(4). This may be bad policy, but it is Congressional policy; and we review it only to determine whether it is rational.
One way of regarding the impact of Congressional policy is to view the PRWORA in a way suggested by the analysis of the Massachusetts Supreme Judicial Court in Doe. What Congress has done in the PRWORA is, in essence, create two welfare programs, one for citizens and one for aliens. Within the aliens-only program, states have the option of including more or fewer aliens. The decision to have separate programs for aliens and citizens is a Congressional choice, subject only to rational-basis review. See Mathews. A state’s exercise of the option to include fewer aliens in its aliens-only program, then, should not be treated as dis*1256crimination against aliens as compared to citizens. That aspect of the discrimination is Congress’s doing — by creating one program for citizens and a separate one for aliens. Rather, what the state is doing is discriminating within the aliens-only program against one class of aliens as compared to other classes of aliens. Cf. Mathews, 426 U.S. at 80, 96 S.Ct. 1883 (“The real question presented by this case is not whether discrimination between citizens and aliens is permissible; rather, it is whether the statutory discrimination within the class of aliens allowing benefits to some aliens but not to others is permissible.”). This discrimination among subclas-sifications of aliens is not based on a suspect classification (such as alienage). The discrimination, rather, is based on nonsus-pect classifications such as work history or military service. We follow the Massachusetts Supreme Judicial Court’s Doe decision in applying rational-basis review to such distinctions. See 773 N.E.2d at 414.
Furthermore, we reject the argument that the PRWORA’s authorization to the states to provide or deny Medicaid benefits to certain aliens runs afoul of the uniformity requirement of the Constitution’s Naturalization Clause. This argument rests largely on dictum in Graham. Graham considered whether Arizona’s durational residency requirement for aliens was authorized by a federal statute. The Court ruled that the statute did not confer such authority. In reaching that conclusion the Court relied in part on the proposition that such statutory authorization would be of questionable constitutionality. The Court wrote:
Under Art. I, § 8, cl. 4, of the Constitution, Congress’ power is to “establish an uniform Rule of Naturalization.” A congressional enactment construed so as to permit state legislatures to adopt divergent laws on the subject of citizenship requirements for federally supported welfare programs would appear to contravene this explicit constitutional requirement of uniformity. Since “statutes should be construed whenever possible so as to uphold their constitutionality,” we conclude that [the federal statute] does not authorize the Arizona 15-year national residency requirement.
403 U.S. at 382-83, 91 S.Ct. 1848 (emphasis added; footnote and internal citation omitted).
It is now our task to determine whether this appearance of unconstitutionality is real. To begin with, we note that Congressional power over aliens derives from more than just the Naturalization Clause. Other sources of Congressional authority include “its plenary authority with respect to foreign relations and international commerce, and ... the inherent power of a sovereign to close its borders.” Plyler v. Doe, 457 U.S. 202, 225, 102 S.Ct. 2382, 72 L.Ed.2d 786 (1982) (Equal Protection Clause is violated by state law authorizing local school districts to deny enrollment to children not legally admitted into the United States).
Indeed, it is not at all clear how the authority “[t]o establish an uniform Rule of Naturalization” is being exercised when Congress restricts welfare benefits to aliens on grounds that have no direct relationship to the naturalization process. Whether the alien is seeking naturalization is not a consideration under the PRWORA. We find it significant that Mathews made no explicit mention of the Naturalization Clause in upholding Congressional authority to establish a residency requirement for aliens to obtain Medicare benefits. Of course, if Congressional authority for the PRWORA’s provisions regarding aliens does not rest on the Naturalization Clause, the limits on the exercise of power under that clause do not necessarily apply; the uniformity requirement is imposed only on a “Rule of Naturalization.”
*1257Moreover, the purpose of the uniformity requirement in the Naturalization Clause is not undermined by the PRWORA’s grant of discretion to the states with respect to alien qualifications for Medicaid benefits. The uniformity requirement was a response to the widely divergent practices among the states under the Articles of Confederation with respect to the requirements to become a naturalized citizen. One state would have a lenient rule, another a very strict rule; yet the Articles required the strict state to treat as a full citizen anyone admitted to citizenship by the lenient state. See Michael Hertz, Limits to the Naturalization Power, 64 Geo. L.J. 1007, 1009-17 (1976); Judith Schenck Koffler, The Bankruptcy Clause and Exemption Laws: A Reexamination of the Doctrine of Geographic Uniformity, 58 N.Y.U. L.Rev. 22, 85-87 (1983). Here, the choice by one state to grant or deny Medicaid benefits to an alien does not require another state to follow suit. We also note that there is reason to believe that at least some Founders did not believe that the Immigration Clause in itself precluded individual states from adopting more lenient standards for naturalization. See U.S. Term Limits Inc., v. Thornton, 514 U.S. 779, 873 n. 13, 115 S.Ct. 1842, 131 L.Ed.2d 881 (1995) (Thomas, J., dissenting).
One final point needs to be addressed. Plaintiffs argue that the language of 8 U.S.C. § 1601(7) illustrates that Congress intended strict scrutiny to apply to state laws that alter legal aliens’ eligibility for jointly funded benefit programs. That section states:
With respect to the State authority to make determinations concerning the eligibility of qualified aliens for public benefits in this chapter, a State that chooses to follow the Federal classification in determining the eligibility of such aliens for public assistance shall be considered to have chosen the least restrictive means available for achieving the compelling governmental interest of assuring that aliens be self-reliant in accordance with national immigration policy.
Id. We think Plaintiffs read too much into this provision. For Congress to say that its statute would survive strict scrutiny is a far cry from' Congress’s stating that the statute should he subject to such scrutiny. We find no reason to believe that Congress wanted to impose on its statute a standard of review more stringent than what the Constitution requires.
5. Appropriateness of Injunctive Relief
Our analysis of Plaintiffs’ equal-protection claim enables us to short-circuit the factor-weighing process for determining whether to grant injunctive relief. The merits issue on this appeal is a pure matter of law. No material facts are disputed. When we determine that a claim lacks merit, we can hardly find an abuse of discretion in denying injunctive relief. To grant relief in that circumstance would be to ignore the demands of the law and express our personal policy views regarding the importance of the interests of the parties and the public.
B. Alleged Procedural Violations
Plaintiffs contend that the procedures used by the Colorado Department in implementing SB 03-176 have three defects: (1) prior to terminating affected Medicaid recipients the Department failed to perform a “full eligibility redetermination” to assess whether the recipients qualified for Medicaid under any other eligibility categories; (2) the state improperly denied certain of the affected recipients an opportunity for a hearing (sometimes referred to as an appeal) to contest the county termination decision before it takes effect; and (3) the state failed to provide timely and adequate notice to the affected, recipients *1258prior to terminating coverage. Plaintiffs claim that each of these deficiencies violates the Medicaid Act, and that the second and third also violate the Due Process Clause of the Fourteenth Amendment. They seek injunctive relief forbidding implementation of SB 03-176 until the procedural deficiencies are corrected.
The district court concluded that Plaintiffs had not shown a substantial likelihood of success with respect to the merits of their procedural claims. After reviewing the Department’s procedures, the court observed that “[t]he evidence adduced at the hearing demonstrated the organized, comprehensive, and proactive manner the Department employed to anticipate and implement SB 03-176 consistent with extant federal and state law and regulations.” Soskin v. Reinertson, 257 F.Supp.2d 1320, 1327 (D.Colo.2003). It stated that “the Department notified the counties [of SB 03-176], instructed them to provide notice to affected recipients, and provided information about how to assess clients, how to determine whether an alien could continue as Medicaid eligible, how to provide notice to each client, and how to calculate the forty working quarters attributable to each client which could affect an alien’s continuing coverage.” Id. at 1328. According to the court, “[S]ystemieally the Department did all that it was required to do under due process to provide timely and sufficient notice to aliens potentially affected by SB 03-176.” Id.
We address Plaintiffs’ three contentions in turn.
1. Redetermination Process
a. System Established by Department
The purpose of the redetermination process is to ascertain whether individuals who lose their status under one eligibility category may qualify under a different eligibility category. After SB 03-176 passed the legislature but before it was signed by the Governor, the Department sent a letter to the counties outlining re-determination procedures. The letter began by describing which legal aliens would be adversely affected by the new law, and which would still be eligible for coverage. It noted that legal permanent residents with 40 quarters of work history would remain eligible, as would honorably discharged veterans and their immediate family members, active duty military personnel and their family members, and certain other specified groups (such as Canadian-born Indians with at least 50% American Indian blood).
The letter then set forth what it described as “the steps necessary to implement [SB 03-176] and stay in compliance with Medicaid eligibility rules.” ApltApp. at 125. The counties were instructed first to compile a list of all Medicaid clients whose status would need to be redetermined as a result of SB 03-176. The Department assisted the counties by attaching to each letter a county-specific report identifying the Medicaid clients whom the Department’s database recorded as having alien registration numbers.
Once the county had compiled the rede-termination list, it was to pull the files of everyone on the list and check them for “immigration verification.” (The parties have not explained what is entailed in an “immigration verification,” nor have we found an explicit explanation in the record, although it appears to encompass obtaining data relating to all qualification categories for aliens, including work history and military service.) If the file included immigration verification from within the preceding three months indicating that the individual met current eligibility requirements, coverage for that person would be maintained. If, however, the file indicated that the individual did not meet the new Medicaid eligibility requirements, the *1259county was to perform an ex parte rede-termination. The letter cryptically stated that “[tjhese individuals can be discontinued without requesting additional verification from the client.” Aplt.App. at 126. The letter does not describe the procedures to follow in performing such an ex parte review.
Because legal permanent residents with 40 creditable work quarters would be eligible for continued Medicaid coverage, the Department’s letter instructed the counties to use the state’s work-history database to “[ijdentify legal permanent residents with 40 quarters of work history.” Id. The letter did not specifically instruct the counties to inquire into the work history of an individual’s spouse during marriage or of a parent while the individual was under 18. See 8 U.S.C. § 1645 (including such work history in calculation of individual’s eligibility). But an attachment to the letter defined “40 Qualifying Quarters” as including those of parents and spouses:
A qualifying quarter means a quarter of coverage as defined under title II of the Social Security Act, which is worked by the alien, and/or
• All the qualifying quarters worked by the spouse of such alien during their marriage and the alien remains married to such spouse or such spouse is deceased, and
• All of the qualifying quarters worked by a parent of such alien while the alien was under age 18....
ApltApp. at 37-38. It appears that those who had 40 verifiable quarters of work history would be removed from the list of aliens to be considered for termination, and that those who did not have the necessary quarters would remain on the list (although neither the letter nor record are altogether clear on this point).
The county officials were then to complete a redetermination of Medicaid eligibility for all who remained on their lists after these initial reviews. The letter directed county officials to send redetermi-nation packets to all aliens who had an unknown immigration status. The Department provided a redetermination form to include in the packet. The form told potentially affected individuals of the impending Medicaid eligibility changes for legal immigrants. It stated:
Due to a new state law, Medicaid eligibility must be redetermined for legal immigrants. Our records show that the following people in your household are legal immigrants. They must have their Medicaid redetermined. Please send us a copy of each person’s current INS card. Also, answer all 5 questions below for each person. If you do not provide the requested information within 10 days from the date listed above, the following people will lose their Medicaid.
Aplt-App. at 132. The five questions for each listed member of the household were: (1) “[What is your] [sjocial security number, if available[?j” (2) “Is this person a U.S. citizen?” (3) “Country of origin?” (4) “Is this person on active duty in the U.S. Armed Forces or a spouse, surviving spouse or child of one?” and (5) “Is this person a veteran, survivor of a veteran, or a dependent of a veteran?” Id.
If the redetermination packet was not returned within 10 business days, the Department directed the counties to send a “Notice of Medicaid Closure” form, along with a second redetermination form. The sample notice form, which apparently was to be used only in cases in which affected recipients did not timely return their rede-termination forms, stated:
*1260Notice of Medicaid Closure
[Name, Address, and Date]
This notice is to tell you that Medicaid has been Closed effective March 30, 2003 for the following family member(s) of your household:
[NAME]
The household member(s) listed above lost their Medicaid because a new state law changed the citizenship requirements for the program. The person(s) listed above did not provide the required verification of their immigration status to complete the redetermination of eligibility. 8.100.7 and 8.100.53 A (10CCR-2505-10)
If you have any questions about this letter, please contact Medicaid Customer Service at (303) 866-3513 or 1-800-221-3943.
This statement certifies that health coverage has been provided to the following client(s) through Colorado Medicaid in accordance with the Health Insurance Portability and Accountability Act.
[Client Name] [Coverage Dates]
Aplt.App. at 136. If still no response was received after the second redetermination packet and Medicaid closure form were sent, the counties were to terminate the individual’s Medicaid coverage. The letter did not direct what form of notice to use for such terminations.
Five days after the Department mailed its letter to the counties, there was a conference call with state and county Medicaid officials to discuss the letter and the implementation process. Forty counties participated in the call. The record does not provide details of what was discussed.
b. Adequacy of the Department’s Process
Plaintiffs assert that the redetermination procedures described above fail to satisfy the requirements set forth in the Medicaid Act and its implementing regulations, because they do not provide for a full redetermination of eligibility of aliens excluded by SB 03-176. They contend that (1) the Department employee in charge of Medicaid conceded at the eviden-tiary hearing that she did not conduct “full redeterminations of eligibility” prior to terminating coverage; and (2) the Department failed to direct the counties to determine whether recipients affected by SB 03-176 are eligible for coverage under any other eligibility category. In particular, they assert that the Department failed to require counties to request work histories of spouses or parents to determine whether they had quarters of work that could be credited to the affected individual.
To support their claim of a full-redeter-mination requirement, Plaintiffs rely on a statute, a regulation, and a few judicial opinions. The statute is 42 U.S.C. § 1396a(a)(8), which states: “A State plan for medical assistance must ... provide that all individuals wishing to make application for medical assistance under the plan shall have opportunity to do so, and that such assistance shall be furnished with reasonable promptness to all eligible individuals.” The regulation is 42 C.F.R. § 435.930(b), which states: “The [state] agency must ... [continue to furnish Medicaid regularly to all eligible individuals until they are found to be ineligible.” Plaintiffs then point out that several courts have held that this federal statute and regulation (or their earlier versions) together require an ex parte redetermination process before termination of a Medicaid recipient. See Crippen v. Kheder, 741 F.2d 102, 104-07 (6th Cir.1984); Mass. Ass’n of Older Ams. v. Sharp, 700 F.2d 749, 751-54 (1st Cir.1983); Stenson v. Blum, 476 F.Supp. 1331, 1339-42 (S.D.N.Y.1979); Olson v. Reagen, No. 85-101-A, 1985 WL 123, at *3, 1985 U.S. Dist. Lexis 20823, at *7-8 (N.D. Iowa Apr. 11, 1985).
*1261Assuming, without deciding, that we would follow those decisions, we observe that none of the decisions (or the laws they rely on) speak to the scope of the redeter-mination review that would be required here, such as what records should be obtained and how they should be analyzed. In Sharp, for example, eligibility would have been immediately apparent. See 700 F.2d at 751-54. The plaintiffs in Sharp had been eligible for Medicaid as recipients of Aid to Families with Dependent Children (AFDC), but they lost their AFDC eligibility as a result of a change in the law that required including stepparent income in determining AFDC eligibility. Id. at 751. Medicaid rules were unchanged, however, so stepparent income was irrelevant to their Medicaid eligibility. Id. at 753-54. The statute, regulation, and case law cited by Plaintiffs do not support the proposition that the Department’s extensive redetermination process was inadequate.
In addition, Plaintiffs make a passing reference to a letter (not included in the record) to the state Medicaid directors from the Director of the Center for Medicare and Medicaid Services, the United States Department of Health and Human Services division that administers Medicaid and promulgates implementing regulations. That letter discusses the redeter-mination process. But Plaintiffs offer no argument why this letter has the force of law.
In any event, Plaintiffs have not produced substantial evidence that the Department’s redetermination process is inadequate. First, we disagree with Plaintiffs’ assertion that Defendant has conceded that the Department failed to require “full redeterminationfs] of eligibility.” Plaintiffs rely on an isolated remark at the district court evidentiary hearing by Diana Maiden, the Department employee in charge of Medicaid services, the same witness who discussed in detail how the Department conducted the elaborate redetermination process discussed above. True, Ms. Maiden said, “[W]e were not asking for a full re-determination on all aspects of eligibility.” ApltApp. at 436. It appears, however, that she meant only that the counties were not required to review eligibility requirements that apply to all Medicaid recipients, but were required only to look at factors applicable to aliens. As noted in Defendant’s brief, “[C]itizenship is a prerequisite to all other eligibility categories with the exception of Supplemental Security Income (“SSI”) and IV-E Foster Care recipients, [so] a full redetermination is unnecessary.” Aple. Br. at 20-21. Ms. Maiden certainly was not saying that counties had no obligation to assess alternative bases of eligibility for those whose existing eligibility was to be eliminated by SB 03-176.
Also, although Plaintiffs have offered (minimal) evidence that one of the named Plaintiffs may in fact remain eligible for Medicaid benefits even if SB 03-176 is lawful, they have not provided evidence that the information establishing eligibility could have been acquired through ex parte procedures, so we have no reason to doubt the adequacy of the state’s ex parte review. And even if an error was made, Plaintiffs have not shown that the error was systematic, rather that being the isolated error of a single worker. Moreover, it appears that lapses in the ex parte review would ordinarily be correctable through information requested from recipients in the redetermination process conducted before termination of benefits. (We note in particular that, as we read the record, Plaintiffs erred in saying that county officials were not instructed to obtain relevant work histories of spouses and parents.)
*1262c. Propriety of Relief Requested
Plaintiffs have not shown a substantial likelihood of success on the merits of then-challenge to the Department’s redetermi-nation process. They also have failed to show a threat of irreparable injury. As we explain below, any person subject to termination of benefits under SB 03-176 is entitled to a hearing before termination. Errors in the redetermination process can be exposed at the hearing.
Given the absence of irreparable injury and the failure to show a substantial likelihood of success on the merits, the district court did not abuse its discretion in denying injunctive relief on this ground, regardless of how one evaluates the remaining two factors relating to the propriety of such relief.
2. Right to Hearing
We next turn to Plaintiffs’ argument that the Department improperly deprived certain recipients of their right to appeal the county’s decision through a pretermination hearing. Plaintiffs complain that those individuals who failed to return their redetermination forms had their eligibility terminated without appeal rights. This is improper, Plaintiffs argue, because the Medicaid Act and Due Process Clause provide recipients a right to a hearing whenever the state takes action to deny services or eligibility. Because we determine that Plaintiffs’ claim succeeds under the Medicaid Act, we need not address constitutional due process.
We start with a brief review of the relevant facts. As part of the redetermi-nation process, the Department instructed counties to send packets to affected individuals, seeking information that would allow the counties to ascertain continued eligibility. If the first packet was not returned within 10 days, a second packet, along with a Notice of Medicaid Closure form, was sent. If the county received no response to the second packet, it was to terminate coverage. As Plaintiffs point out, Department employee Ms. Maiden testified that those individuals who failed to respond to two redetermination packets were terminated without appeal rights (though she did indicate that those recipients could reapply for Medicaid and have their eligibility reinstated if they came forward with adequate documentation).
Turning now to the governing law, the Medicaid Act, 42 U.S.C. § 1396a(a)(3), states that a state agency must “provide for granting an opportunity for a fair hearing before the State agency to any individual whose claim for medical assistance under the [state] plan is denied or is not acted upon with reasonable promptness.” Additionally, one of the implementing regulations, 42 C.F.R. § 431.220, directly addresses when hearings are required; it states:
When a hearing is required.
(a) The State agency must grant an opportunity for a hearing to the following:
(1) Any applicant who requests it because his claim for services is denied or is not acted upon with reasonable promptness.
(2) Any recipient who requests it because he or she believes the agency has taken an action erroneously.
(b) The agency need not grant a hearing if the sole issue is a Federal or State law requiring an automatic change adversely affecting some or all recipients.
42 C.F.R. § 431.220 (emphasis added). If a hearing is requested, the affected individual maintains eligibility pending the outcome of the hearing. 42 C.F.R. § 431.231; Volume 8, Colorado Medicaid Manual § 8.057.5. Thus, the hearing contemplated by the regulations is in effect a pre-termination hearing.
*1263Defendant relies on the exception created by § 431.220(b) to argue that the Department was not required to provide hearings to individuals whose eligibility was eliminated by SB 03-176. Because Plaintiffs contest only Defendant’s failure to provide a hearing to those individuals who were terminated based on their failure to return the redetermination forms, we limit our analysis to that issue.
We do not agree that § 431.220(b) applies here. In our view a law imposing an automatic change in benefits is not “the sole issue.” Affected individuals who did not timely return their redetermination forms could contest several factual matters. For example, they could assert that they did return the form but that the county lost it or failed to process it; or they could argue that they never received either of the two redetermination forms the county allegedly mailed. They might also be able to argue that they are eligible based on an alternative eligibility category — 40 quarters of work, veteran status, etc. The potential for these various factual disputes makes inapplicable the hearing exception provided by § 431.220(b).
Such potential factual disputes renders Defendant’s reliance on Benton v. Rhodes, 586 F.2d 1 (6th Cir.1978), misplaced. Benton involved a new state policy that categorically terminated certain types of supplies and services — over-the-counter drugs, medical supplies, non-emergency ambulatory coverage, dental services, speech therapy, etc. — that were provided to all Medicaid recipients. Id. at 2. The court held that no hearings were required because the sole issue was legal, not dependent upon the factual circumstances of individual recipients. See id. at 3^4. There was no factual scenario in which people would otherwise qualify for the supplies and services that the state law discontinued. See id.
Because § 431.220(b) is inapplicable, the other provisions of § 431.220 remain effective. Specifically, “[t]he State agency must grant an opportunity for a hearing to ... (2) Any recipient who requests it because he or she believes the agency has taken an action erroneously.” 42 C.F.R. § 431.220. No such hearing rights were recognized by the Department for those individuals who failed to return their rede-termination forms. Accordingly, we conclude that Plaintiffs have shown a substantial likelihood of success on the merits of this issue. The other factors clearly weigh in favor of Plaintiffs. We therefore reverse in part the district court’s denial of a preliminary injunction. Defendant should be preliminarily enjoined from denying a request for an appeal by one whose benefits are to be terminated for failure to return a redetermination form.
3. Sufficiency of Notice
Plaintiffs’ final argument is that the notice forms used by the Department to terminate eligibility are facially invalid because “they fail to provide an adequate statement of appeal rights or an explanation of the basis for the termination sufficient to enable recipients to identify themselves as having been terminated erroneously.” Aplt. Br. at 48. They contend that such information is required by the Medicaid Act and regulations, as well as by the Due Process Clause.
The Medicaid Act’s implementing regulations set forth requirements for notice related to the right to appeal and the reasons for termination. Addressing appeal rights, 42 C.F.R. § 431.206 states that “[a]t the time of any action affecting [a recipient’s] claim,” id. § 431.206(c),
(b) The agency must ... inform every applicant or recipient in writing—
(1) Of his right to a hearing;
*1264(2) Of the method by which he may obtain a hearing; and
(3) That he may represent himself or use legal counsel, a relative, a friend, or other spokesman.
42 C.F.R. § 431.206. Furthermore, 42 C.F.R. § 431.210 states that the notice must contain—
(a) A statement of what action the State ... intends to take;
(b) The reasons for the intended action;
(c) The specific regulations that support, or the change in Federal or State law that requires, the action;
(d) An explanation of—
(1) The individual’s right to request an evidentiary hearing if one is available, or a State agency hearing; or
(2) In cases of an action based on a change in law, the circumstances under which a hearing will be granted; and
(e) An explanation of the circumstances under which Medicaid is continued if a hearing is requested.
42 C.F.R. § 431.210.
The constitutional right to due process may also impose notice requirements. See, e.g., Goldberg v. Kelly, 397 U.S. 254, 267-68, 90 S.Ct. 1011, 25 L.Ed.2d 287 (1970) (when public welfare benefits are terminated, due process “principles require that a recipient have timely and adequate notice detailing the reasons for a proposed termination”).
Plaintiffs’ brief alleges that inadequate notice was provided by each of seven different forms of notice used to implement SB 03-176 — the Notice of Medicaid Closure Form quoted above and six others. We share Plaintiffs’ concern about the adequacy of notice provided by the forms. The notice of appeal rights on certain forms appears to be inaccurate. Also, there is room for improvement in some of the language explaining why benefits are being terminated. Nevertheless, the factual record is so deficient that the district court did not abuse its discretion in failing to find a likelihood of success on the merits. The briefs do not explain, and the record before us does not reveal, critical information regarding the notices, such as: (1) Which notice went to what people? (2) Under what circumstances was the notice sent? (3) What other information, if any, had previously been provided to the recipients? (4) Were notices other than the seven challenged by Plaintiffs sent to persons to be terminated? This information is essential to an assessment of whether language in a notice is likely to be misleading to those who actually receive it.
This same lack of information also makes it impossible to determine who, if anyone, is likely to suffer injury in the absence of better notice. It would be inappropriate to issue an injunction with respect to all alien Medicaid recipients if only a fraction are receiving improper notice.
In the absence of an adequate showing of either a likelihood of success or irreparable injury, the district court did not abuse its discretion in denying injunctive relief. The sole exception relates to notice to those who were terminated for failure to return the redetermination forms. Defendant admits that those persons were not notified of the right to request a hearing. We therefore REVERSE the district court’s denial of a preliminary injunction requiring that such persons be advised of the right to request a pre-termination hearing. Moreover, we express the hope that Defendant will review all notices so that it can revise and resend (or instruct the counties to resend) notice to those of the 3,500 affected persons who may have received inadequate notice.
III. CONCLUSION
We VACATE our injunction pending appeal and AFFIRM the district court’s de*1265nial of Plaintiffs’ motion for a preliminary injunction, except that we REVERSE in part and REMAND to the district court for entry of a preliminary injunction prohibiting Defendant from terminating benefits to any member of the class for failure to return redetermination forms unless the member has been given notice of the right to request a pre-termination hearing.