McKEAGUE, J., delivered the opinion of the court, in which NORRIS, J., joined. GILMAN, J. (pp. 537-44), delivered a separate dissenting opinion.
OPINION
McKEAGUE, Circuit Judge.
This is an appeal from a judgment dismissing claims challenging Tennessee’s driver license law as violative of certain aliens’ right to equal protection and right to travel. On due consideration of plaintiffs’ complaint in light of the parties’ appellate arguments, we affirm the district court’s judgment that the complaint fails to state a claim upon which relief can be granted.
I. BACKGROUND
For purposes of this appeal, plaintiffs in the action below include: the League of United Latin American Citizens (“LU-LAC”), a not-for-profit organization dedicated to the advancement of the interests of the Hispanic population in the United States; Yolanda Lewis, a citizen of Mexico and resident of Tennessee, proceeding on her own behalf and on behalf of her minor son, Sergio Chavez; and Alex M. Siguenza, a citizen of Nicaragua and resident of Tennessee. Defendants, sued in their official capacities, are Phil Bredesen, Governor of Tennessee; and Fred Phillips, Commissioner of the Tennessee Department of Safety.
In June 2004, plaintiff Alex Siguenza attempted to renew his Tennessee driver license in Nashville. When he admitted that he was neither a United States citizen nor a lawful permanent resident, he was advised that he could not be issued a new driver license, but only a certificate for driving. On July 9, 2004, plaintiff Yolanda Lewis attempted to obtain a Tennessee identification card for her 8-year old son, Sergio Chavez, in Nashville. When she disclosed that Sergio was neither a United States citizen nor a lawful permanent resident, she was told that he was not entitled to any state-issued identification document. As a non-lawful permanent resident, plaintiff Lewis, too, is not eligible for a driver license under Tennessee law.
Plaintiffs commenced this putative class action in the Middle District of Tennessee on July 12, 2004. Plaintiff LULAC proceeds on behalf of its members (over 115,-000 throughout the United States); Lewis proceeds on behalf of herself and her minor son and all others similarly situated; and Siguenza proceeds on behalf of himself and all others similarly situated. The first amended complaint contains nine counts. Only two are relevant to this appeal. Both challenge provisions of 2004 Public Acts Chapter 778, amending Tennessee’s driver license law, which became effective July 1, 2004. In count I, plaintiffs proceed under 42 U.S.C. § 1983 and allege that Tenn. Code Ann. § 55 — 50—321(c)(1)(C), conditioning issuance of a driver license upon proof of United States citizenship or lawful permanent resident status, is a classification based on alienage that denies them equal protection of the law. In count VI, plaintiffs seek a declaratory judgment to the effect that Tenn.Code Ann. § 55-50-321(c)(1)(C), by denying a driver license to some aliens, impermissibly burdens aliens’ fundamental right to travel. That lawful temporary resident aliens may obtain a “certificate for driving” instead, pursüant to Tenn.Code Ann. § 55-50-331(g), is said not to be an adequate substitute, because [527]*527the certificate for driving, unlike a driver license, is explicitly “not valid for identification.” Tenn.Code Ann. § 55-50-102(6). Plaintiffs moved for a preliminary injunction to enjoin implementation of Chapter 778 and enjoin issuance of certificates for driving to aliens in lieu of driver licenses. Plaintiffs also asked the court to require defendants to convert all certificates for driving already issued during 2004 into driver licenses.
In an opinion and order dated September 28, 2004, the district court denied plaintiffs’ motion for preliminary injunction. League of United Latin American Citizens v. Bredesen, No. 3:04-0613, 2004 WL 3048724 (M.D.Tenn. Sept.28, 2004). This ruling has not been appealed. On November 23, 2004, the court granted the state defendants’ motion to dismiss, thereby dismissing the claims contained in counts I and VI, which are the subject of this appeal. Incorporating by reference the reasoning set forth in its opinion denying preliminary injunction, the district court held that neither the equal protection claim nor the right to travel claim stated a claim upon which relief can be granted. The court concluded that issuance of a certifícate for driving instead of a driver license does not infringe aliens’ right to travel. Id. at *4-5. The court also concluded that the classification, treating illegal aliens and lawful temporary resident aliens differently than lawful permanent resident aliens, does not discriminate against a suspect class and does not burden a fundamental right. The court therefore held that the classification is subject to “rational basis” scrutiny. Applying rational basis scrutiny, the court went on to hold that the classification is rationally related to legitimate governmental purposes and is therefore not violative of equal protection. Id. at *5-6. The district court dismissed the claims under Fed.R.Civ.P. 12(b)(6). A final judgment order was entered on January 19, 2006 and this appeal followed.
II. ANALYSIS
A. Standard of Review
Whether the district court properly dismissed plaintiffs’ claims under Rule 12(b)(6) is a question of law subject to de novo review. Kottmyer v. Maas, 436 F.3d 684, 688 (6th Cir.2006). The court must construe the complaint in the light most favorable to plaintiffs, accept all well-pled factual allegations as true and determine whether plaintiffs undoubtedly can prove no set of facts consistent with their allegations that would entitle them to relief. Id. Though decidedly liberal, this standard does require more than bare assertions of legal conclusions. Bovee v. Coopers & Lybrand C.P.A., 272 F.3d 356, 361 (6th Cir.2001). Plaintiffs’ obligation to provide the “grounds” of their entitlement to relief requires more than labels and conclusions or a formulaic recitation of the elements of the cause of action. Bell Atlantic Corp. v. Twombly, — U.S. -, 127 S.Ct. 1955, 1964-65, 167 L.Ed.2d 929 (2007). The factual allegations, assumed to be true, must do more than create speculation or suspicion of a legally cognizable cause of action; they must show entitlement to relief. Id. at 1965. To state a valid claim, a complaint must contain either direct or inferential allegations respecting all the material elements to sustain recovery under some viable legal theory. Id. at 1969.
B. Standing
In granting the state defendants’ motion to dismiss, the district court rejected their arguments that plaintiffs lacked standing to prosecute their claims. LULAC, 2004 WL 3048724 at *2. Accepting the allegations of plaintiffs’ complaint at face value, the district court was satisfied that LU-[528]*528LAC met the requirements of organizational standing as defined in American Civil Liberties Union of Ohio Foundation, Inc. v. Ashbrook, 375 F.3d 484, 489 (6th Cir.2004).1
The district court was similarly unpersuaded by the state defendants’ contention that only illegal aliens, who are not members of a suspect class and are therefore entitled only to minimal protection under the Equal Protection Clause, would even arguably suffer the sort of harm that would confer standing to bring these claims, because only illegal aliens are denied both a driver license and a certificate for driving under the new Tennessee law.2 The court took note of plaintiffs’ allegations that lawful temporary resident aliens, as a result of being issued a “not valid for identification” certificate for driving in lieu of a driver license, could experience difficulties in producing “satisfactory evidence of identification.” See First Amended Complaint ¶¶ 22-27. This “satisfactory evidence of identification” is required under various provisions of Tennessee law in order to render a person charged with a misdemeanor offense or traffic rule violation eligible for issuance of a citation in lieu of arrest. See, e.g., TenmCode Ann. § 40-7-118(e)(3).3 Hence, plaintiffs impliedly allege that the denial of a driver license (a) makes it necessary for a lawful temporary resident alien to carry his or her passport and/or other immigration documents for personal identification purposes; and (b) increases the risk that he or she will be subject to arrest for any suspected minor infraction simply because a law enforcement officer may find his or her proof of identification unfamiliar and therefore “unsatisfactory.” The district court was satisfied that such alleged potential difficulties are sufficient to make out the requisite injury to confer standing on lawful temporary resident aliens who reside in Tennessee.
On appeal, the state defendants do not challenge this latter ruling and we find no error in it.4 As to LULAC’s organization[529]*529al standing, however, the state defendants renew then’ challenge, with a different twist. They contend, with reference to the standards set forth in ACLU of Ohio, that the complaint does not allege that any of the individually named plaintiffs is a LU-LAC member or that any LULAC member is a resident of Tennessee otherwise eligible for a Tennessee driver license or certificate for driving. Absent such allegations, i.e., that a member is subject to an actual or threatened injury, defendants contend LULAC cannot satisfy the requirements of organizational standing.
Plaintiffs respond first that this particular standing argument, having not been raised in the district court, has been effectively waived. Indeed, the general rule is that the court of appeals will not review issues raised for the first time on appeal. Barner v. Pilkington N. Am., 399 F.3d 745, 749 (6th Cir.2005). However, inasmuch as standing is a threshold requirement, it must be addressed, even in the first instance on appeal, because the court of appeals is obliged to satisfy itself of its own jurisdiction before proceeding to the merits of the appeal. Children’s Healthcare is a Legal Duty, Inc. v. Deters, 92 F.3d 1412, 1419 (6th Cir.1996) (Batchel-der, J., concurring) (collecting cases); Steel Co. v. Citizens for a Better Environment, 523 U.S. 83, 102, 118 S.Ct. 1003, 140 L.Ed.2d 210 (1998) (“Standing to sue is part of the common understanding of what it takes to make a justiciable case.”).
Secondly, notwithstanding any technical deficiency in their complaint, plaintiffs insist the record establishes that both individually named plaintiffs, Yolanda Lewis and Alex Siguenza, who have alleged that they are residents of Tennessee, see First Amended Complaint ¶¶ 7, 9, are also members of LULAC. Indeed, their respective affidavits, filed in support of plaintiffs’ motion for preliminary injunction, state that they are members of LU-LAC. The affidavits also state that each is lawfully present in the United States and at least imply, consistent with the allegations of their complaint, that each is indeed a resident of Tennessee. Accepted at face value, the unrefuted affidavits appear to satisfactorily answer defendants’ reformulated standing challenge, demonstrating that LULAC members are affected by the Chapter 778 changes to Tennessee’s driver license law and that LULAC therefore has organizational standing.
Defendants argue that their standing challenge was made in their motion to dismiss under Rule 12(b)(6) and that the sufficiency of plaintiffs’ complaint should be tested based solely on the strength of its allegations, without assistance from matters outside the pleadings, like affidavits. Yet, this precise argument, regarding the complaint’s failure to expressly allege that LULAC members were harmed by Chapter 778, was not made below, at a time when plaintiffs could have moved for and been freely granted leave to amend their complaint to cure the defect. See Fed.R.Civ.P. 15(a) (leave to amend “shall be freely granted when justice so requires”). Now, as the argument is raised first on appeal, it would not serve justice to dismiss the appeal at this point because of a technical pleading deficiency, in the face of undisputed record facts confirming that plaintiffs actually do have standing and did have standing to prosecute their claims when the complaint was filed. See Cleveland Branch, NAACP v. City of Parma, Ohio, 263 F.3d 513, 524 [530]*530(6th Cir.2001) (standing is to be assessed under the facts existing when the complaint was filed). Considering the present record in light of defendants’ particular standing challenge, we conclude that plaintiffs have adequately cleared this “qualifying hurdle.” See Children’s Healthcare, 92 F.3d at 1419.
We therefore find no error in the district court’s holding that plaintiffs have standing to proceed with their claims.5
C. Equal Protection Claim
1. Rational Basis or Heightened Scrutiny?
(a) Suspect Class
The district court’s dismissal of plaintiffs’ equal protection claim is based on the conclusion that the classification drawn by Chapter 778, treating illegal aliens and lawful temporary resident aliens differently than lawful permanent resident aliens, is subject to “rational basis” scrutiny. Ordinarily a state law classification that “neither burdens a fundamental right nor targets a suspect class” will be upheld “so long as it bears a rational relation to some legitimate end.” Vacco v. Quill, 521 U.S. 793, 799, 117 S.Ct. 2293, 138 L.Ed.2d 834 (1997). Plaintiffs contend the district court erred in applying rational basis scrutiny. They argue that issuance of certificates for driving instead of driver licenses to aliens who are not lawful permanent residents represents a classification that discriminates against a suspect class, aliens, and infringes their fundamental right to travel. These effects of Tennessee’s driver license law are said to demand heightened scrutiny, requiring the court to “carefully examine” the governmental interest claimed to justify the discrimination and determine “whether that interest is legitimate and substantial” and “whether the means adopted to achieve the goal are necessary and precisely drawn.” Nyquist v. Mauclet, 432 U.S. 1, 7, 97 S.Ct. 2120, 53 L.Ed.2d 63 (1977) (quoting Examining Board v. Flores de Otero, 426 U.S. 572, 605, 96 S.Ct. 2264, 49 L.Ed.2d 65 (1976)).
The district court recognized that aliens are “persons” and are protected under the Equal Protection Clause. LULAC, 2004 WL 3048724 at *3, n. 1. The court further recognized that a classification based on alienage is suspect, citing City of Cleburne, Texas v. Cleburne Living Center, Inc., 473 U.S. 432, 105 S.Ct. 3249, 87 L.Ed.2d 313 (1985). Id. at *3. However, in reasoning clear and succinct, the court concluded that Chapter 778 does not discriminate based on alienage:
This case is not about “citizens” versus “aliens.” Plaintiffs argue that classifications based on alienage are inherently suspect. But the statute at issue does not classify persons based on alienage. The statutory classification in this case is between citizens and lawful permanent resident aliens on the one hand, and illegal aliens and those aliens who are not permanent lawful residents, on the other hand. Thus, the classification created by the drivers’ license legislation is not between aliens and citizens. The drivers’ license law does not distinguish among persons because of a protected classification. For instance, aliens can [531]*531qualify for either a drivers’ license or a drivers’ certificate based on legitimate criteria other than alienage. Instead, the classification is based on the legality of the alien’s presence in the country under federal law (lawful permanent resident aliens vs. illegal aliens) and/or the length of time the federal government has authorized the alien to stay in this country (permanent vs. temporary). Thus, the court is not persuaded that the legislation burdens a suspect class, and should be subjected to strict scrutiny analysis.
Id. (footnote omitted). The district court went on to hold that illegal aliens are not a suspect class, citing Plyler v. Doe, 457 U.S. 202, 223, 102 S.Ct. 2382, 72 L.Ed.2d 786 (1982), and that the subclass of aliens legally admitted on a temporary basis is not a suspect class. Id. at *4.
On appeal, plaintiffs neither argue nor cite authority for the proposition that illegal aliens are a suspect class. They assert only the interests of a distinct subclass of aliens: those who are lawful temporary residents; i.e., aliens who are not lawful permanent residents; aliens whose authorized presence is tied to a specific purpose or defined period of time.6 They argue that a classification which affects only some but not all aliens, must still be scrutinized strictly. In support, they rely primarily on Nyquist v. Mauclet, where “close judicial scrutiny” was applied to strike down a state law that prevented somé but not all “resident aliens” from receiving state financial assistance for higher education. 432 U.S. at 7-8, 97 S.Ct. 2120. Indeed, the Nyquist court held that the fact that the challenged statute discriminated against only a subclass of aliens did not obviate the need to apply heightened scrutiny. What was important to the Nyquist court was that the state law classification was “directed at aliens and that only aliens were harmed by it.” Id. at 9, 97 S.Ct. 2120.
The district court distinguished Nyquist on three bases: (1) the harm flowing from the classification; (2) the fact that the Nyquist classification affected not just temporary, but also permanent resident aliens; and (3) the gravity of the state interest justifying the classification. L 17-LAC, 2004 WL 3048724 at *4, n. 3. We conclude that all three distinctions are material and we agree with the district court that they compel a different outcome here than in Nyquist.
In Nyquist, a subclass of aliens, including permanent resident aliens, was denied a significant privilege under New York law, state financial assistance for higher education. The Nyquist court noted the unfairness implicit in disallowing permanent resident aliens, who were required to pay their full share of the taxes that supported the financial aid programs, from equal participation in those programs. 432 U.S. at 12, 97 S.Ct. 2120. Under Tennes[532]*532see’s driver license law, in contrast, lawful temporary resident aliens are not denied driving privileges or any other privilege. Inasmuch as a certificate for driving issued to a lawful temporary resident alien undis-putedly affords him or her the same driving privileges that a driver license affords a citizen or lawful permanent resident alien, the instant subclass of aliens hardly suffers any cognizable harm as a direct result of the classification.
In fact, plaintiffs’ complaint is devoid of any allegation of actual harm suffered by a plaintiff. Their claims are premised rather on the threat of harm stemming from the possibility that the passport or other personal identification document a lawful temporary resident alien may carry in lieu of a driver license may not be accepted by a law enforcement officer or other third party as “satisfactory evidence of identification,” to the alien’s detriment. This could lawfully occur only if there were objectively reasonable grounds to question the accuracy of the alien’s passport or other identification paper. See n. 3, supra. While such potential difficulties stemming from the classification may represent an injury within the zone of interests protected by the Equal Protection Clause sufficient to confer standing, the fact that the claimed harm is so indirect and conjectural is not insignificant in determining whether heightened scrutiny of the state law classification is appropriate. The harm flowing from the denial of financial aid in Nyquist was clearly more substantial than the hypothetical inconvenience or hardship posed by Tennessee’s issuance of certificates for driving, instead of driver licenses, to lawful temporary residents.
The district court also distinguished Ny-quist on the ground that Tennessee’s interests in maintaining highway safety and public safety are more compelling than were New York’s interests in limiting higher education financial aid to persons who were or would become eligible to vote. The district court deemed the issuance of certificates for driving to represent a reasonable exercise of traditional police power, allowing temporary resident aliens to operate motor vehicles without requiring the state to vouch for their identity. LU-LAC, 2004 WL 3048724 at *4-5 (noting state’s legitimate interest in preventing use of its governmental machinery to facilitate concealment of illegal aliens and other foreign nationals who may be involved in terrorist activities).
The district court’s observation that Tennessee’s public safety interest is stronger than the interest presented in Nyquist is plainly accurate. See Nyquist, 432 U.S. at 10-12, 97 S.Ct. 2120 (exposing weaknesses of New York’s asserted interests). Of course, the strength of the governmental interest supporting the classification is most appropriately considered if and after the classification is found to result in discriminatory harm to members of a suspect class. Yet, the governmental purpose is not entirely immaterial in determining the appropriate level of scrutiny. That the harm complained of is practically de minimis and results from the exercise of traditional police power are factors that distinguish this case from Nyquist and counsel in favor of deferential review of the classification.
Still, it is the district court’s third basis for distinguishing Nyquist that is most important. In Nyquist, the plaintiffs were lawful permanent resident aliens who were subject to discriminatory harm and were treated as members of a suspect class. The reason this is critical is well explained in LeClerc v. Webb, 419 F.3d 405 (5th Cir.2005). In LeClerc, the Fifth Circuit noted that, although classifications based on alienage are inherently suspect, the Supreme Court has employed strict scrutiny [533]*533with respect to only one subclass of aliens: lawful permanent residents. Id. at 415-16. The state laws presented in cases such as Nyquist were deemed to warrant “close judicial scrutiny because they took positions seemingly inconsistent with the congressional determination to admit the alien to permanent residence.” Id. at 417 (quoting Foley v. Connelie, 435 U.S. 291, 295, 98 S.Ct. 1067, 55 L.Ed.2d 287 (1978)) (emphasis added in LeClerc).
The LeClerc court explained at length why lawful temporary resident aliens, or “nonimmigrant aliens,” are not entitled to the same protection as lawful permanent resident aliens. Id. at 417-20. In short, the court recognized that permanent resident aliens are “virtual citizens” who are “legally entrenched in society” but who lack the ability to participate in the political process. Id. at 417. This inability renders them “a prime example of a discrete and insular minority for whom [] heightened judicial solicitude is appropriate.” Id. (quoting In re Griffiths, 413 U.S. 717, 721, 93 S.Ct. 2851, 37 L.Ed.2d 910 (1973)). Permanent resident aliens are similarly situated to citizens in economic, social, and civic conditions as well. Like citizens, they pay taxes, support the economy, serve in the armed forces, and are entitled to reside permanently in the United States. Id. at 418.
Temporary resident aliens, on the other hand, are admitted to the United States only for the duration of their authorized status, are not permitted to serve in the U.S. military, are subject to strict employment restrictions, incur differential tax treatment, and may be denied federal welfare benefits. Id. at 418-19. Because of these aggregate factual and legal differences, the LeClerc court declined to hold that nonimmigrant lawful temporary resident aliens comprise a suspect class entitled to the extraordinary protection of strict scrutiny: “We decline to extend the Supreme Court’s decisions concerning [permanent] resident aliens to different alien categories when the Court itself has shied away from such expansion.” Id. at 419. The court went on to hold that rational basis review is the appropriate standard for evaluating state law classifications affecting nonimmigrant aliens. Id. at 420.
We find the analysis set forth in LeClerc to be persuasive. There are abundant good reasons, both legal and pragmatic, why lawful permanent residents are the only subclass of aliens who have been treated as a suspect class. This case presents no compelling reason why the special protection afforded by suspect-class recognition should be extended to lawful temporary resident aliens. Because the instant classification does not result in discriminatory harm to members of a suspect class, it is subject only to rational basis scrutiny.
The appropriateness of this conclusion is underscored by the fact that the classification drawn by Tennessee law, unlike that presented in Nyquist, is in no way inconsistent with federal law, but rather mirrors it. As the district court observed, Chapter 778 does not deny any benefit of state law to lawful temporary resident aliens. It merely serves to deny state-issued proof of identification to any alien whose presence the federal government has refrained from permanently authorizing, so as to avoid the appearance that the State of Tennessee is vouching for his or her identity. The alien issued a certificate for driving is free to drive on the highways of Tennessee and free to use his or her own passport or other identification papers as needed. Despite plaintiffs’ efforts to depict Chapter 778 as reflective of invidious discrimination against aliens warranting close judicial scrutiny, the classification drawn is, on its [534]*534face, sensible and directly derivative of aliens’ status under immigration law.7, 8
(b) Fundamental Right to Travel
Plaintiffs correctly argue that even in the absence of a suspect class, a classification warrants strict scrutiny if it burdens the exercise of a fundamental right. They argue that denial of a driver license that may be used for identification purposes burdens their fundamental right to travel. The district court recognized that the Supreme Court has recognized a protected right to interstate travel, Saenz v. Roe, 526 U.S. 489, 500, 119 S.Ct. 1518, 143 L.Ed.2d 689 (1999), and the Sixth Circuit has recognized a protected right to intrastate travel, i.e., “a right to travel locally through public spaces and roadways,” Johnson v. City of Cincinnati, 310 F.3d 484, 494-98 (6th Cir. 2002). LULAC, 2004 WL 3048724 at *4. Yet, the district court held the protected right to travel does not embody a right to a driver license or a right to a particular mode of transportation, citing Duncan v. Cone, 2000 WL 1828089 (6th Cir.) (unpublished) (holding “there is no fundamental right to drive a motor vehicle.”); John Doe No. 1 v. Georgia Dep’t of Public Safety, 147 F.Supp.2d 1369, 1375 (N.D.Ga.2001) (observing that “the Circuit Courts have uniformly held that burdens on a single mode of transportation do not implicate the right to interstate travel,” and collecting cases). Further, the district court held that the right to travel, whatever its eon-[535]*535tours, is not infringed by Chapter 778 because a person who receives a certificate for driving is able to operate a motor vehicle just like a person who receives a driver license. LULAC, 2004 WL 3048724 at *5. Potential difficulties that may be experienced by one who does not have a driver license to use for identification purposes were held not to implicate the right to travel.
In Saenz, the Supreme Court identified three components of the right to travel: “It protects the right of a citizen of one State to enter and to leave another State, the right to be treated as a welcome visitor rather than an unfriendly alien when temporarily present in the second State, and, for those travelers who elect to become permanent residents, the right to be treated like other citizens in that State.” 526 U.S. at 500, 119 S.Ct. 1518. Plaintiffs have not identified, nor have we uncovered, any authority for the proposition that lawful temporary resident aliens enjoy the same fundamental right to travel that citizens do. Yet, even assuming temporary resident aliens’ right to travel is constitutionally protected, the question remains whether such right is impermissibly burdened by Chapter 778.
A state law implicates the right to travel when it actually deters travel, when impeding travel is its primary objective, or when it uses a classification that serves to penalize the exercise of the right. Attorney General of New York v. Soto-Lopez, 476 U.S. 898, 903, 106 S.Ct. 2317, 90 L.Ed.2d 899 (1986). Tennessee’s issuance of certificates for driving, which confer all the same driving privileges as driver licenses, is clearly not designed primarily to impede travel and can hardly be said to deter or penalize travel. The state’s denial of state-issued photograph identification to temporary resident aliens may arguably result in inconvenience, requiring the bearer of a certificate for driving to carry other personal identification papers, but this inconvenience can hardly be said to deter or penalize travel. To the extent this inconvenience burdens exercise of the right to travel at all, the burden is incidental and negligible, insufficient to implicate denial of the right to travel. See Town of Southold v. Town of East Hampton, 477 F.3d 38, 54 (2d Cir.2007) (collecting cases recognizing that even citizens do not have a constitutional right to the most convenient form of travel). Something more than a negligible or minimal impact on the right to travel is required before strict scrutiny is applied. State of Kansas v. United States, 16 F.3d 436, 442 (D.C.Cir.1994).
Plaintiffs contend it is conceivable that they could prove the certificate for driving might not be accepted by an insurance company as satisfactory evidence of identification. If they could not obtain automobile insurance, they argue, they would be prevented from driving legally in Tennessee. While the argument is “conceivable,” it is hardly plausible. Plaintiffs offer no reason to believe any insurance company would find a passport or other personal identification document, presented in conjunction with a certificate for driving, inadequate for issuance of automobile insurance.9 Even if such an eventuality were deemed plausible, its occurrence and the resulting incidental “burden” on travel would hardly be attributable to Chapter [536]*536778, but rather to a private entity’s exercise of business discretion. Plaintiffs’ argument is simply too speculative, factually and legally, to justify the conclusion that their right to travel is impermissibly burdened by issuance of a certificate for driving that is not valid for identification.
Accordingly, we find no error in the district court’s determination that rational basis scrutiny applies, because Chapter 778 implicates neither a suspect class nor a fundamental right.
2. Rational Relationship to Legitimate Government Purpose
Under traditional rational basis scrutiny, a state law classification will be upheld “so long as it bears a rational relation to some legitimate end.” Vacco, 521 U.S. at 799, 117 S.Ct. 2293. The reason for such deferential review is explained as follows:
The initial discretion to determine what is “different” and what is “the same” resides in the legislatures of the States. A legislature must have substantial latitude to establish classifications that roughly approximate the nature of the problem perceived, that accommodate competing concerns both public and private, and that account for limitations on the practical ability of the State to remedy every ill. In applying the Equal Protection Clause to most forms of state action, we thus seek only the assurance that the classification at issue bears some fair relationship to a legitimate public purpose.
LeClerc, 419 F.3d at 420 (quoting Plyler, 457 U.S. at 216, 102 S.Ct. 2382).
The district court accepted that Chapter 778’s classification was designed to serve homeland security interests by indicating to third parties that the State of Tennessee does not vouch for the identity of the person holding a certificate for driving while at the same time allowing the holder of the certificate to validly operate a motor vehicle in Tennessee. The court concluded that the balancing of interests achieved by issuing certificates for driving to aliens who are not lawful permanent residents is rationally related to this purpose.
Plaintiffs do not directly challenge this aspect of the district court’s ruling. They argue that, irrespective of the level of scrutiny employed, the classification must be carefully examined to ensure that it rationally furthers some legitimate, articulated purpose. This careful examination can hardly be conducted, they contend, based on the pleadings alone pursuant to Rule 12(b)(6).
In urging this “careful” or “stringent” examination, plaintiffs rely on cases that addressed discriminatory treatment of suspect classes, i.e., cases that employed heightened scrutiny. See Examining Board, 426 U.S. at 605, 96 S.Ct. 2264; Griffiths, 413 U.S. at 721-22, 93 S.Ct. 2851. However, a classification such as Chapter 778, subject to rational basis review, is accorded a “strong presumption of validity.” Heller v. Doe by Doe, 509 U.S. 312, 319, 113 S.Ct. 2637, 125 L.Ed.2d 257 (1993). The state has no obligation to produce evidence sustaining the rationality of the classification. Id. at 320, 113 S.Ct. 2637. To overcome this strong presumption of validity, a challenger has the burden of negating all possible rational justifications for the classification. Id.; Gean v. Hattaway, 330 F.3d 758, 771 (6th Cir.2003).
Plaintiffs have not carried this burden either in their pleadings or in their appellate arguments. The district court’s conclusion that the state’s interest — in refraining from vouching for the identity of aliens who have not been granted permanent resident status by the federal government but whose permission to stay here is [537]*537tied to a specific purpose or period of time — is legitimate and rationally served by Chapter 778 has not been shown to be erroneous. For the reasons set forth above, it is apparent that, even upon viewing the allegations of plaintiffs’ complaint in the light most favorable to plaintiffs, they fail to set forth a factual basis upon which relief can be granted under the Equal Protection Clause. That the classification might ultimately be shown to have been drawn unnecessarily broadly and to result in differential treatment and even inconvenience is of no consequence where-the classification is subject only to deferential rational basis scrutiny. See Heller, 509 U.S.. at 321, 113 S.Ct. 2637 (observing that a classification does not fail rational basis review simply because it is not made with “mathematical nicety” or because it results in some inequality). This is because, under rational basis review, the court is obliged “to accept a legislature’s generalizations even when there is an imperfect fit between means and ends.” Id.
Accordingly, plaintiffs have failed to demonstrate that the challenged classification is not rationally related to a legitimate government purpose. The district court’s dismissal of their equal protection claim for failure to state a claim upon which relief can be granted must therefore be affirmed.
D. Right to Travel Claim
Plaintiffs have asserted their constitutionally protected right to travel in two contexts: first, in support of their argument in support of their count I equal protection claim that Chapter 778 should be subjected to strict scrutiny; and second, in support of their separate count VI claim for infringement of their fundamental right to travel. As outlined above, the district court determined that plaintiffs’ claims fail to adequately allege that their right to travel is actually burdened by Chapter 778. For the same reasons that the district court properly concluded that the asserted infringement of the right to travel does not warrant strict scrutiny of Chapter 778, it also properly concluded that count VI fails to state a proper claim. We therefore uphold the district court’s dismissal of the count VI.
III. CONCLUSION
Plaintiffs’ arguments for heightened scrutiny of Chapter 778 are based on allegations too conclusory and conjectural to justify the inferences required to satisfy the essential elements of their claims. Their claims do not, therefore, withstand scrutiny even under the decidedly liberal standard of Rule 12(b)(6). Accordingly, the judgment of the district court, dismissing plaintiffs’ count I claim for denial of equal protection as well as their count VI claim for violation of their right to travel, is AFFIRMED.