This is an interlocutory appeal from the order of the United States District Court for the Northern District of Georgia denying the plaintiffs’ motion for class certification and dismissing a pendent state law claim for lack of jurisdiction.1 We affirm.
I. BACKGROUND
The plaintiffs are former employees of Delta Air Lines, Inc. (“Delta”), who retired between July 23,1992 and January 1,1993. On May 16, 1994, they commenced this action against Delta and various Delta officials based upon alleged violations of the Employment Retirement Income Security Act, 29 U.S.C. §§ 1001 et seq. (“ERISA”), and also asserting a state law breach of contract cause of action. On June 3, 1994, they filed an amended complaint to add certain defendants. According to the allegations of the complaint,2 the facts giving rise to the lawsuit are as follows.3
On July 23,1992, Delta announced impending changes in the medical insurance benefits plan provided by the company for its employees and retirees.4 Employees were told that those who retired after January 1, 1993 would receive reduced benefits and be required to pay higher premiums than persons who retired prior to that date. In subsequent weeks, the company disseminated further information, both orally and in writing, which stated that individuals who retired on or before January 1, 1993, would be “grandfathered” with respect to their current medical benefits, meaning, they would be entitled to the same level of coverage throughout the course of their retirement and would not be affected by any future changes in the medical insurance plan offered by the airline. In addition, Delta assured its employees that it did not intend at that time to offer any package of enhanced retirement incentives in the future. The latter declarations were made orally during retirement planning seminars conducted by the company and “in numerous conversations with potential Delta retirees.” (Rl-3 at ¶ 45).
The complaint further alleged that the plaintiffs chose their retirement dates in reliance on Delta’s promises that their level of medical coverage and premiums would remain constant throughout their retirement and that no improved retirement package was in the planning stage at the time they made their decision. After they retired, however, the company reduced the level of their medical benefits and required them to pay higher premiums for coverage. Also, contrary to the statements made denying a plan to offer an enhanced benefits package in the future, retirement terms more favorable than those extended to the plaintiffs were contemplated by the airline prior to January 1, 1993 and in fact were offered to certain eligible employees on August 23, 1993 (hereinafter referred to as the “Special Retirement Plan”).
These allegations formed the basis for the first four counts of the complaint. Count I urged that, when the plaintiffs retired on or before January 1, 1993, they entered into a bilateral contract with Delta, enforceable under ERISA, which mandated that the company continue to provide the same medical benefits package to the plaintiffs throughout their retirement years. Count II asserted that by making false assurances to the plaintiffs regarding the continuation of the terms *454of their retirement benefits and by denying the intention to offer the Special Retirement Plan in the future, Delta breached its fiduciary duty to the plaintiffs in violation of ERISA. Count III charged that Delta fraudulently induced the plaintiffs to retire on or before January 1,1993 for the purpose of preventing their participation in the Special Retirement Plan. Count IV claimed that by falsely informing the plaintiffs that no better retirement package would be forthcoming after January 1, 1993, and then extending such a package to subsequent retirees, Delta unlawfully discriminated against certain benefits plan participants in favor of others, contrary to ERISA.
In addition to the ERISA causes of action contained in Counts I through IV, Count V of the complaint alleged a suit for breach of contract under Georgia law. This claim was predicated upon allegations that Delta made repeated promises to the plaintiffs during their employment that retirees who were at least fifty-two years’ old and who had worked for the airline for at least ten years would be entitled to certain flying privileges throughout their retirement. However, on October 26, 1993, the company eliminated flight privileges for any retiree who had accepted employment with another airline or affiliate.
On August 12, 1994, the plaintiffs moved for class certification pursuant to Fed. R.Civ.P. 23. In a brief in support of the motion, the plaintiffs identified the putative class as over 1,800 “former employees of Delta Air Lines, Inc., who retired from employment at Delta Air Lines between the dates of July 23, 1992 and January 1, 1993, inclusive.” (Rl-11, Brief at 2). The plaintiffs alleged that the causes of action set forth in Counts I through V of the complaint could best be pursued in the form of a class action because, inter alia, they involved common issues of law and fact and the claims of the class representatives were typical of those of the class as a whole.
Thereafter, the defendants moved to dismiss Count V of the complaint for lack of subject matter jurisdiction on the ground that it was unrelated to the federal ERISA claims asserted in Counts I through IV and lacked the requisite diversity of citizenship. The defendants also opposed class certification, contending in part that the ERISA claims were not amenable to class-wide proof because they turned on each retiree’s individual reliance on the alleged assurances made by Delta. Furthermore, the defendants argued, the requirements of commonality and typicality necessary for class certification were not met because the claims depended, all or in part, upon a variety of alleged oral representations, thereby necessitating proof of the particular statements made to each retiree.5 The defendants conceded that “if Plaintiffs claims were based on uniform written documents received and relied on by the entire class, commonality and typicality could be present.” (R2-16 at 36). They maintained, however, that the plaintiffs failed to carry their burden of proof on this score because they offered no evidence that Delta ever issued such uniform written assurances.
The plaintiffs then filed a reply to the motion to dismiss Count V and to the defendants’ opposition to class certification. In support of the latter issue, the plaintiffs submitted, inter alia, copies of a newsletter disseminated by Delta to its employees and several intracompany memorandums, all of which discussed the changes in the medical benefits plan effective January 1, 1993.6
In an order dated November 4, 1994, the district court granted the defendants’ motion to dismiss Count V for lack of jurisdiction and denied the plaintiffs’ motion for class certification. With respect to Count V, the *455court found that the requirements for supplemental jurisdiction under 28 U.S.C. § 1367 were not present because the state law claim alleged therein did not sufficiently involve the same facts, occurrences, witnesses or evidence as the federal ERISA claims and it was separately maintainable from the ERISA counts. On the issue of class certification of the ERISA causes of action, the court found that the plaintiffs failed to furnish proof rising to the level imposed by federal law which would demonstrate commonality and typicality. In particular, the court stated that the plaintiffs
have not shown that the questions of fact in each affected retiree’s case are common to any other retiree’s case. According to the plaintiffs, Delta made the representations that are at issue in this case orally, during several retirement planning seminars, and in writing, in various mailouts and fliers posted on bulletin boards. Plaintiffs must show not only whether each retiree was aware of these representations, but more importantly, the extent to which each retiree relied on the alleged representations in making his or her retirement decision. These are factual issues that must be resolved independently for each retiree.
(R2-24 at 8).
On November 21, 1994, the plaintiffs moved for reconsideration of the district court’s order, or in the alternative, for the certification necessary to seek an interlocutory appeal in accordance with 28 U.S.C. § 1292(b). See supra note 2. The court denied the request for reconsideration, but did issue the § 1292(b) certification. This court subsequently permitted the appeal.7
II. STANDARD OF REVIEW
The district court’s dismissal of Count V of the complaint for lack of subject matter jurisdiction is a question of law which is reviewed de novo on appeal. McMillian v. FDIC, 81 F.3d 1041, 1045 (11th Cir.1996). We consider the court’s denial of class certification under an abuse of discretion standard. Washington v. Brown & Williamson Tobacco Corp., 959 F.2d 1566, 1569 (11th Cir.1992); Coon v. Georgia Pacific Corp., 829 F.2d 1563, 1566 (11th Cir.1987).
III. DISCUSSION
A. Dismissal of Count V.
We first address the district court’s dismissal of Count V for lack of subject matter jurisdiction. There is no question in this case that diversity of citizenship does not exist, thus, subject matter jurisdiction over the state law allegations in Count V depends upon the existence of that aspect of supplemental jurisdiction formerly known as pendent claim jurisdiction. See Palmer v. Hospital Auth. of Randolph County, 22 F.3d 1559, 1566 (11th Cir.1994). The presence of supplemental jurisdiction is governed by 28 U.S.C. § 1367. Subsection (a) of that statute defines the power of the federal courts to hear supplemental claims. Palmer, 22 F.3d at 1566. It provides in relevant part that
in any civil action of which the district courts have original jurisdiction, the district courts shall have supplemental jurisdiction over all other claims that are so related to claims in the action within such original jurisdiction that they form part of the same case or controversy under Article III of the United States Constitution.
28 U.S.C. § 1367(a). The district court had original jurisdiction (in this ease, federal question. jurisdiction) over the ERISA counts. The court’s power to adjudicate Count V therefore turns on whether the state law cause of action alleged therein is so related to an ERISA ground that they form part of the same case or controversy. In deciding whether a state law claim is part of the same case or controversy as a federal issue, we look to whether the claims arise from the same facts, or involve similar occurrences, witnesses or evidence. Palmer, 22 F.3d at 1566.
*456We agree with the district court that Count V of the complaint does not arise from the same case or controversy as the ERISA causes of action. The record shows that the flight privileges at issue in Count V were not part of an ERISA benefits plan and were administered by .a different department of Delta. Moreover, the alleged facts underlying Count V are completely unrelated to the allegations in support of the ERISA claims. The only factor they share in common is that the airline’s decisions with respect to ERISA benefits and flight benefits affected certain retirees. This does not provide a sufficient nexus between the federal and state causes to support supplemental jurisdiction. We consequently affirm the dismissal of Count V. In so doing, we necessarily find that the issue of class certification as to Count V is moot.
B. Denial of Class Certification.
Next, we consider the district court’s denial of class treatment of Counts I, II, III and IV, the ERISA grounds. Class certification is governed by Fed.R.Civ.P. 23. Rule 23 permits the maintenance of a class action when (1) the class is so numerous that join-der of all of its members is impracticable, (2) questions of law or fact common to the class are present, (3) the claims or defenses of the representative parties are typical of the claims or defenses of the class and (4) the representative parties will sufficiently protect the interests of the class. Fed.R.Civ.P. 23(a).8 The burden of proving these prerequisites is on the representative party or parties seeking class certification. Gilchrist v. Bolger, 733 F.2d 1551, 1556 (11th Cir.1984); Nelson v. United States Steel Corp., 709 F.2d 675, 678-79 (11th Cir.1983).
As stated earlier, the district court’s decision to deny class certification was based upon the absence of commonality and typicality. These factors provide the necessary link between the class representatives and the class members. Washington, 959 F.2d at 1569 n. 8. Although the issues of commonality and typicality are separate inquiries, proof of each also “tend[s] to merge.” Id.
The plaintiffs contend that commonality and typicality are present with respect to Count I because, although they and the putative class members received the alleged assurances through different media and from different sources, the airline issued a uniform message to all employees concerning the terms of their future medical benefits plan, which depended on their retirement on or before January 1, 1993. Likewise, they claim, Delta issued identical information to all members of the putative class concerning the Special Retirement Plan, that is, that no such plan was contemplated for a later date.
In response, the defendants essentially argue that the ERISA claims have no merit. They maintain that Delta reserved the right to amend or discontinue the plaintiffs’ medical benefits at any time.9 Thus, the defendants insist that the plaintiffs cannot prove, class-wide or otherwise, the formation of the *457purported bilateral contract alleged in Count I. In addition, the defendants reiterate that evidence of individual reliance on a variety of purported oral representations is necessary with respect to all of the ERISA counts and state that, consequently, each plaintiffs claims must be determined on a case-by-case basis.
We stress initially that the merits of the plaintiffs’ claims are not before us. See Eisen v. Carlisle & Jacquelin, 417 U.S. 156, 178, 94 S.Ct. 2140, 2153, 40 L.Ed.2d 732, 749 (1974) (quoting Miller v. Mackey Int’l, 452 F.2d 424, 427 (5th Cir.1971) (“ ‘In determining the propriety of a class action, the question is not whether the plaintiff or plaintiffs have stated a cause of action or will prevail on the merits, but rather whether the requirements of Rule 23 are met.’ ”). Nevertheless, “evidence relevant to the commonality requirement is often intertwined with the merits.” Nelson, 709 F.2d at 679. Accordingly, it sometimes is necessary to “to probe behind the pleadings before coming to rest on the certification question.” General Tel. Co. of the Southwest v. Falcon, 457 U.S. 147, 160, 102 S.Ct. 2364, 2372, 72 L.Ed.2d 740, 752 (1982).
The issue of commonality with respect to the Count I contract claim is fundamentally different than the commonality that must be shown to support class certification of the Special Retirement Plan allegations described in Counts II through IV. We find that the claims relating to the Special Retirement Plan are not susceptible to class-wide proof. Even if the plaintiffs are able to prove that Delta disseminated a false and uniform message to all potential retirees that no such plan was in the works at the time they made their decision to retire, they would also have to show that all members of the class would have deferred their retirement in the hope that they would be eligible for the Special Retirement Plan to be offered in the future.10 This sort of decision would necessarily have been highly individualized for each potential retiree.
On the other hand, the merits of the Count I contract cause depend simply on evidence of the formation of the bilateral contract alleged therein. This will require proof of written plan documents which notified the putative class that the terms of their medical benefits plan would remain constant throughout their retirement if they retired on or before January 1,1993.
ERISA requires that welfare benefit plans be governed by written plan documents which are to be prepared and filed in compliance with ERISA’s reporting and disclosure requirements.... Accordingly, any retiree’s right to lifetime medical benefits at a particular cost can only be found if it is established by contract under the terms of the ERISA-governed benefit plan document.
Alday v. Container Corp. of America, 906 F.2d 660, 665 (11th Cir.1990) (citations omitted), cert. denied, 498 U.S. 1026, 111 S.Ct. 675, 112 L.Ed.2d 668 (1991). This type of claim seems, on the surface, to be amenable to class-wide proof. So far, however, the plaintiffs have failed to demonstrate the existence of such written plan documents.11 The plaintiffs’ reliance on the alleged uniform oral statements guaranteeing the same level of medical benefits throughout their retirement is of no help because “there [is] no federal common law right to promissory estoppel under ERISA in cases involving oral amend*458ments to or modifications of employee plans governed by ERISA.”12 Id. at 666.
In Alday, this court stated in dicta that ERISA fiduciaries might not be insulated from liability on the basis of the formal written plan documents where contradictory and fraudulent promises are made in informal communications for the purpose of deceiving employees with respect to their benefits. Id. at 666 n. 15. We voice no opinion as to whether the plaintiffs could state a claim under such circumstances. Even if they could, none of the evidence of record to date, which consists solely of informal company communications, supports the plaintiffs’ allegations that they were assured that the terms of their medical coverage would never change.13 With this record as our only source of information, we can find no abuse of discretion by the district court in denying class certification as to Count I of the complaint.
Of course, if, through further proceedings, the plaintiffs are able to clarify and better support the need for class certification, the district court remains free to revisit the issue.14 The determination of whether a class should be certified should be made “[a]s soon as practicable after the commencement of an action.” Fed.R.Civ.P. 23(c)(1). Additional discovery on the issue and a hearing may be helpful.15 See Washington, 959 F.2d at 1570-71. We leave any further development of the class treatment issue with respect to Count I to the sound discretion of the district court.16 We simply hold that, at this stage of *459the proceedings, the district court did not abuse its discretion in denying class certification on the record before us.
IV. CONCLUSION
In accordance with the foregoing, we AFFIRM the dismissal of Count V for lack of subject matter jurisdiction, we AFFIRM the denial of class certification with respect to Counts I, II, III and IV and we REMAND the case to the district court for further proceedings.
. This court granted the plaintiffs' petition for interlocutory review pursuant to 28 U.S.C. § 1292(b), which permits appeals to be taken in civil cases from decisions not otherwise appeal-able when the district court certifies that the "order involves a controlling question of law as to which there is substantial ground for difference of opinion and that an g immediate appeal from the order may materially advance the ultimate termination of the litigation.” 28 U.S.C. § 1292(b).
. We refer to the amended complaint as the complaint.
. At this preliminary stage of the case and for purposes of this appeal, we must treat the allegations of the complaint as true.
. A notice issued to "All Members of the Delta Family" stated that, due to adverse economic forces and to avoid "downsizing,” it was necessary for the airline to substantially and permanently reduce its costs, which, among other things, would require revision of the company-provided medical and dental benefits package. (R2-20, Exhibit I).
. According to the allegations of the complaint, Count I was based upon oral and written representations. The claims involving the Special Retirement Plan resulted solely from alleged oral promises.
. The evidence submitted by the plaintiffs included company memorandums dated both before and after January 1, 1993. {See generally R2-20, Exhibits). Only the newsletter, which was dated August 27, 1992, and those memorandums issued prior to January 1, 1993 could have affected the timing of the plaintiffs' retirement. An affidavit of one of the plaintiffs, Felton E. Hudson, was also proffered. It states that “[s]uch memos were posted on company bulletin boards.” {Id. at Exhibit B, ¶ 6). No objections to the inclusion of this evidence in the record were made by Delta. We presume that it is properly before us.
. When the district court certifies that interlocutory review of an order is warranted, the court of appeals may, in its discretion, permit an appeal to be taken if application is made to it within ten days after entry of the district court's certification. 28 U.S.C. § 1292(b); General Television Arts, Inc. v. Southern Ry. Co., 725 F.2d 1327, 1330 (11th Cir.1984).
. If the requirements of Fed.R.Civ.P. 23(a) are met, the district court must go further and determine whether the facts before the court satisfy Fed.R.Civ.P. 23(b). That subsection provides that class actions are appropriate only when (1) the prosecution of separate actions would create a risk of inconsistent verdicts or where individual adjudications would, as a practical matter, be dispositive of the interests of class members who are nonparties; or (2) the party opposing the class has acted or refused to act on grounds generally applicable to the putative class such that declaratory or injunctive relief with respect to the class as a whole would be appropriate; or (3) questions of law or fact common to members of the class predominate over issues affecting individual members and class adjudication is preferable to other methods of litigation for purposes of a fair and efficient resolution of the controversy. Because the district court found that the Rule 23(a) prerequisites of commonality and typicality were not present, it did not reach the Rule 23(b) issue. Our review on appeal is therefore confined to the district court's subsection (a) determination.
. In support of this assertion the defendants refer to a statement contained in a supplement to Delta's benefits handbook, which described changes in post-retirement medical and dental benefits effective Januaiy 1, 1992. The supplement states, "[a]s always, Delta reserves the right to change, modify, amend or discontinue the benefits described in this supplement of the Benefits Handbook at any time.” (Appendix of Ap-pellees, Tab A, Exhibit 2; see also id. at Tab J, Exhibit 77). This evidence was not made a part of the record in the district court. Consequently, we do not consider it on appeal.
. The evidence contained in the record regarding the Special Retirement Plan discloses that it was offered only to a select group of employees who were at least fifty-two years' old on November 1, 1993 and who worked in particular departments of the airline targeted for downsizing. Participation was also limited to a certain number of persons in those departments to fit the business needs of the airline. (R2-20, Exhibits E, F). There was no guarantee that persons eligible for the program would be allowed to enroll. If requests to retire under the plan exceeded availability, acceptance was based upon seniority. {Id. at Exhibit F). It is most unlikely that all members of the putative class were eligible to participate in the program or would have delayed their retirement on the chance that they might be selected. In any event, the plaintiffs made no showing on this issue.
. As noted earlier, the written documentation made a part of the record in support of the motion for class certification consists of a company newsletter and intracompany memorandums.
. A federal common law claim of equitable es-toppel may come into play based upon oral interpretations of ambiguous ERISA plan documents. Alday, 906 F.2d at 666; Kane v. Aetna Life Ins., 893 F.2d 1283, 1285-86 (11th Cir.), cert. denied, 498 U.S. 890, 111 S.Ct. 232, 112 L.Ed.2d 192 (1990). “However, estoppel is not available either for oral modifications (as opposed to interpretations) or when the written plan is unambiguous." Glass v. United of Omaha Life Ins. Co., 33 F.3d 1341, 1347 (11th Cir.1994). The plaintiffs do not allege in this case that the controlling ERISA plan documents were ambiguous.
. The newsletter defined “grandfathered” persons as "includ[ing] those individuals who were Delta employees as of August 31, 1991 and were age 52 or older as of January 1, 1992.” (R2-20, Exhibit H). It also stated that “[i]f you elect to retire early prior to age 62 on January 1, 1993, the early retirement medical and dental contribution will not apply. However, the service related contribution may apply if you were not part of the grandfathered group." Id. It is not clear from this language exactly what it meant to be “grandfathered." Moreover, although the evidence indicates that Delta told potential retirees that certain employee contributions would be waived for persons in the "grandfathered” group who retired on or before January 1, 1993, nothing in the record supports the plaintiffs' claims that they were also told that the particular type of medical benefits included in the ERISA plan would be provided in perpetuity.
. For example, the plaintiffs may yet be able to produce written plan documents in support of Count I. We caution, however, that the documentation currently in the record indicates that Delta made certain differentiations among various groups of retirees depending upon an employee's age at retirement, years of service and whether some of that service was with another airline. Thus, even if class certification were appropriate, it might be necessary to define and provide for various subclasses. But, we also note that at this point the plaintiffs' case appears to be based solely upon a theory of promissory estoppel, which is not cognizable under ERISA. Alday, 906 F.2d at 666. If the plaintiffs are unable to state a claim for relief, any question as to class certification will be moot. See id. at 667.
. Although a hearing is not required prior to granting or denying a motion for class certification, Grayson v. K Mart Corp., 79 F.3d 1086, 1099 (11th Cir.1996), such a procedure may, in an appropriate case, aid the court in deciding the issue.
. Although the issue of class certification should be resolved in the early stages of a case if possible, prior discovery is often necessary to sufficiently define the proper scope of an alleged class or subclass. Here, the plaintiffs moved for class treatment prior to conducting any discovery, traveling solely on the broad allegations of the complaint. Such an approach may be acceptable in some cases, but this is not one of them. Because the entitlement to ERISA benefits is controlled by formal plan documents, the analysis of any claim arising from the alleged failure to comply with an ERISA plan must begin with an examination of those documents, which will also define the class or classes of persons governed thereby. The record in the present case shows that discovery began on August 17, 1994 and continued until March 22, 1995, when it was stayed by the district court pending the resolution of this appeal. The plaintiffs failed to make the pertinent ERISA plan documents a part of the record during this time. By suggesting that the district court may, in its discretion, reopen the class certification issue after further development of the case, we do not mean to imply that the court should do so.