Petitioner-appellant Gary Graham (Graham), convicted in Texas court of the capital murder during robbery of Bobby Lambert and sentenced to death, appeals the district court's denial of his third habeas petition under 28 U.S.C. § 2254.1 We conclude that Graham has not adequately exhausted his state remedies as required by section 2254(b) & (c), and, despite the state's having waived exhaustion below, we determine, in the exercise of our discretion, not to accept the waiver, and we accordingly vacate the district court's judgment and remand the case to the district court with directions to dismiss the petition without prejudice for failure to exhaust state remedies.

We generally summarize the background and procedural history of this case as follows.

About 9:30 p.m. on May 13, 1981, in the parking lot of a Safeway Food Store in Houston, Texas, Bobby Lambert, a customer at the store, was shot and killed by a lone black male who was attempting to rob him. The perpetrator promptly left the scene without being apprehended. Following his arrest for another offense about a week later, Graham, then seventeen years old, was charged with the capital murder of Lambert, and was convicted and sentenced to death in October 1981 following a jury trial in the 182nd Judicial District of Harris County, Texas.2 At the guilt-innocence stage of the trial, among other evidence presented by the state, Wilma Amos, Daniel Grady (since deceased), and Bernadine Skillern (now Benton) testified to the shooting incident. However, Skillern was the only trial witness to identify Graham as the shooter. The other witnesses did not testify that Graham was not or did not resemble the perpetrator, but merely stated they did not get a good enough look at, or sufficiently recall, the perpetrator's face to make an identification. Skillern testified she identified Graham in a May 26 photographic display and in a May 27 police station "line-up," and she identified him in open court. The defense presented no evidence at the guilt-innocence stage. However, defense counsel attacked Skillern's identification in vigorous cross-examination of her,3 and in argument emphasized the failure of the other witnesses to identify Graham and urged that the evidence failed to show Graham was the perpetrator. At the punishment stage, the state presented evidence that during the period May 14 through May 20, 1981, Graham robbed some thirteen different victims at nine different locations, in each instance leveling either a pistol or a sawed-off shotgun on the victim. Two of the victims were pistol-whipped, one being shot in the neck; a sixty-four-year-old male victim was struck with the vehicle Graham was stealing from him; and a fifty-seven-year-old female victim was kidnaped and raped. There was also testimony that Graham's reputation in the community for being a peaceful and law-abiding citizen was bad. The only defense evidence was the testimony of Graham's stepfather and grandmother, generally as to his good and nonviolent character.

On his direct appeal, Graham's conviction and sentence were affirmed by the Texas Court of Criminal Appeals in an unpublished per curiam opinion. Graham v. State, 671 S.W.2d 529 (Tex.Crim.App.1984) (table). Certiorari review in the United States Supreme Court was not sought.

Graham, represented by new counsel, filed a state habeas petition in July 1987, contending, inter alia, that he was incompetent to be executed, that the Texas capital punishment scheme was constitutionally defective for various reasons and did not allow the jury to adequately consider mitigating evidence, including his youth, and that he received ineffective assistance of counsel. Counsel was alleged to be ineffective in numerous respects, including the failure to adequately investigate and to interview and call alibi witnesses, and not allowing Graham to testify. A competency examination was conducted, and an evidentiary hearing was held in January 1988 before state district judge Shipley (who had not presided at Graham's trial) at which Graham and other witnesses, including three alibi witnesses, William Chambers, Mary Brown, and Dorothy Shield, testified, as did also Graham's trial counsel, Ronald Mock and Chester Thornton. On February 9, 1988, the state trial habeas court entered findings of fact and conclusions of law in all respects adverse to Graham, finding, among other things, that Graham was not incompetent, that his counsel advised him not to testify but told him he had a right to do so and that the decision was his, that Graham never told counsel he wanted to testify, and that (inter alia ):

"4. Prior to trial, counsel [who had been appointed to represent Graham June 12, 1981] reviewed the information in the State's file several times.

5. On numerous occasions prior to trial, counsel met with the applicant and attempted to discuss the facts of the case with him. The applicant stated only that he did not commit the robbery-murder and that he had spent the evening with a girlfriend whose name, appearance, and address the applicant could not remember.

6. Although defense counsel made numerous inquiries of applicant, he did not give his defense counsel the names of any potential alibi witnesses, nor did the applicant tell his counsel where he had been and what he had been doing on the night of the instant offense, May 13, 1981.

7. No person ever presented himself to defense counsel as an alibi witness, either before, during or after trial.

8. Specifically, the applicant did not furnish his counsel with the names or addresses of Dorothy Shield, Williams Chambers, Mary Brown, or Lorain [sic] Johnson as potential alibi witnesses.

9. This court finds that the testimony of William Chambers, Mary Brown and Dinah Miller concerning Gary Graham's whereabouts on May 13, 1981 is not credible testimony.

10. Gary Graham was aware that an investigator was working with defense counsel in connection with the defense of his case.

11. Counsel for applicant hired an investigator, Merv West, who assisted them in investigating and interviewing possible defense witnesses."

The state habeas trial court concluded that in all respects Graham had received effective assistance of counsel. The Court of Criminal Appeals, in an unpublished per curiam order with reasons issued February 19, 1988, denied habeas relief, essentially on the basis of the habeas trial court's findings.

Shortly thereafter, Graham, through his new counsel, filed his first federal habeas petition in the district court below. He asserted, among other things, that his age at the time of the offense constitutionally prevented his execution, that he was not mentally competent to be executed, that the Texas capital sentencing scheme did not allow adequate consideration of his youth and other mitigating circumstances, and that his counsel was ineffective in diverse respects including the following, viz: failing to conduct adequate pretrial investigation, failing to interview all the witnesses, failing to adequately cross-examine Skillern, failing to bring forth alibi witnesses, failing to develop a proper trial strategy, failing to call more than two witnesses at sentencing, and failing to allow Graham to testify. The district court denied relief and we denied CPC. Graham v. Lynaugh, 854 F.2d 715 (5th Cir.1988). We specifically reviewed the allegations concerning ineffective assistance of counsel and the state habeas court findings in respect thereto, id. at 721-22, and concluded "that Graham has failed to overcome the presumption that the state court's findings were correct." Id. at 722. The Supreme Court in a per curiam order granted certiorari, vacated our judgment and remanded the case to this Court "for further consideration in light of Penry v. Lynaugh," 492 U.S. 302, 109 S. Ct. 2934, 106 L. Ed. 2d 256 (1989). Graham v. Lynaugh, 492 U.S. 915, 109 S. Ct. 3237, 106 L. Ed. 2d 585 (1989). On remand, the same panel of this Court, in part I of its opinion on remand, reinstated all of its 1988 opinion except section IIB thereof (854 F.2d at 718-720) dealing with whether the Texas capital sentencing scheme allowed adequate consideration of mitigating evidence, particularly youth. Graham v. Collins, 896 F.2d 893, 894 (5th Cir.1990). The 1990 panel decision went on to hold that the Texas capital sentencing scheme, contrary to Penry, did not allow adequate consideration of Graham's youth, and accordingly vacated his death sentence. Id. at 898. We then took the case en banc and ultimately affirmed the denial of habeas relief. Graham v. Collins, 950 F.2d 1009 (5th Cir.1992) (en banc). The en banc Court specifically reinstated part I of the 1990 panel opinion (896 F.2d at 894), thus reinstating all of the 1988 panel opinion except part IIB thereof (854 F.2d at 718-720). Id., 950 F.2d at 1013 n. 4. The en banc Court went on to reject Graham's contention that the Texas capital sentencing scheme did not allow adequate consideration of his mitigating evidence, particularly his youth. Id. Accordingly, we reinstated our prior mandate affirming the district court's dismissal of Graham's habeas petition. Id. at 1034. The United States Supreme Court subsequently affirmed, addressing only the youth-Penry issue and holding that any claim that the Texas capital sentencing scheme did not allow adequate consideration of youth was barred under Teague v. Lane, 489 U.S. 288, 109 S. Ct. 1060, 103 L. Ed. 2d 334 (1989). Graham v. Collins, 506 U.S. 461, 113 S. Ct. 892, 122 L. Ed. 2d 260 (1993).4

On April 20, 1993, Graham, through counsel, filed his second state habeas. In this petition, Graham first again urged that his counsel was ineffective for failing to develop or present defense evidence or meaningfully test the prosecution's evidence, and that Graham had thus been "condemned to die for a crime that he almost certainly did not commit." Graham also asserted that the trial court's voir dire erroneously equated "deliberateness," as used in the first punishment issue, with "intent" as relevant to guilt or innocence. Finally, it was asserted that the punishment issues did not adequately allow consideration of Graham's youth.5 This petition was supported by a March 31, 1993, affidavit of the investigator (West) retained by Graham's trial counsel; April 17, 1993, affidavits by Malcolm Stephens and wife Lorna Stephens that they came on the crime scene just after the shooting, saw a young black man run away (not followed in the lot by anyone in a car, as Skillern had testified she followed the perpetrator) who was about 5'5"' tall (a line-up chart indicated Graham was 5'9"' tall); affidavits of Wilma Amos (April 15, 1993) and Ronald Hubbard (April 18), who were present at the scene; affidavit of Mary Brown (April 18), Graham's wife; and affidavits of William Chambers (April 18), Graham's cousin, Dorothy Shields (April 18), and Loraine Johnson (April 18). Graham filed a supplement to his petition early the morning of April 26 adding a claim that because he was actually innocent his execution would be unconstitutional, relying on Herrera v. Collins, 506 U.S. 390, 113 S. Ct. 853, 122 L. Ed. 2d 203 (1993). This supplement was supported by an April 26, 1993, affidavit of Malcolm Stephens. The state filed a reply, supported by affidavits (including an April 21, 1993, affidavit of Mock, an April 22, 1993, affidavit of West, and a March 26, 1993, affidavit of Skillern). Later the same day, April 26, the state habeas trial court, Judge Shipley, entered findings and conclusions, and supplemental findings, recommending denial of relief. The court adopted its previous findings and conclusions entered February 9, 1988, respecting Graham's first state habeas,6 found that the April 18, 1993, alibi affidavits of Chambers, Brown, Shield, and Loraine Johnson were "not credible," that West's March 31, 1993, affidavit, in light of his April 22, 1993, affidavit showing loss of memory, was "not reliable," that Amos' April 15, 1993, affidavit "is not credible," that Hubbard and the Stephenses did not see the actual shooting and their affidavits do not undermine Skillern's identification,7 and that Skillern's "testimony is credible." The court concluded that the allegations of defective performance of counsel for failing to adequately investigate, interview witnesses, and call alibi witnesses had been rejected in the previous state habeas and hence need not be considered again, and, alternatively, that neither defective performance in any respect nor resultant prejudice was shown.8 The court further concluded:

"6. The applicant's claim of actual innocence, independent of any constitutional infirmity in his trial, is not cognizable in state or federal habeas proceedings; therefore, the applicant is not entitled to state or federal relief based on such claim.

7. Alternatively, even assuming the applicant's claim of actual innocence is cognizable, the applicant's showing of 'innocence' falls far short of the threshold showing which would have to be made in order to trigger its consideration and relief based thereon. Thus, the applicant fails to show deficient performance, much less harm, in counsels' representation at trial."

On April 27, 1993, the Court of Criminal Appeals denied habeas relief in a per curiam order stating "The Court has reviewed the record. The findings and conclusions entered by the trial court are supported by the record and upon such basis the relief sought is denied." Ex parte Graham, 853 S.W.2d 564, 565 (Tex.Crim.App.1993), cert. denied, 508 U.S. 945, 113 S. Ct. 2431, 124 L. Ed. 2d 651 (1993). Graham, on April 28, 1993, then filed a section 2254 petition with the district court below; however, the Texas governor having granted Graham a thirty-day stay of execution the same day, Graham then dismissed his section 2254 petition without prejudice before the state could answer it. Fed.R.Civ.Proc. 41(a)(1)(i). Also on April 28, 1993, Graham filed a petition for certiorari in the United States Supreme Court seeking review of the April 27, 1993, order of the Court of Criminal Appeals. Thereafter, Graham's execution was set for June 3, 1993. On May 14, 1993, Graham filed with the Court of Criminal Appeals a motion for reconsideration of its April 27, 1993, order. On May 24, 1993, the Supreme Court denied Graham's petition for certiorari directed to the April 27, 1993, order of the Texas Court of Criminal Appeals. Graham v. Texas, 508 U.S. 945, 113 S. Ct. 2431, 124 L. Ed. 2d 651 (1993). On June 2, 1993, the Court of Criminal Appeals overruled Graham's motion for reconsideration but ordered Graham's execution "stayed for 30 days pending the resolution of Johnson v. Texas by the United States Supreme Court." Ex parte Graham, 853 S.W.2d 565, 567 (Tex.Crim.App.1993).9

On June 24, 1993, the Supreme Court issued its opinion in Johnson v. Texas, 509 U.S. 350, 113 S. Ct. 2658, 125 L. Ed. 2d 290 (1993), holding that the Texas capital sentencing scheme adequately allowed consideration of the defendant's youth as a mitigating factor.

Graham then filed in the Court of Criminal Appeals a motion to continue the stay of execution and for remand to the state trial court for an evidentiary hearing on his claims of ineffective assistance of counsel, based on newly discovered evidence. In a per curiam order issued July 5, 1993, the Court of Criminal Appeals denied the motion to continue stay, and denied the motion for remand without prejudice to presenting the claims to the state trial court. Ex parte Graham, 853 S.W.2d 565 at 570-71 (Tex.Crim.App.1993). The Court of Criminal Appeals stated (id. at 571):

"Applicant has filed a Motion to Continue the Stay of Execution and for Remand for Evidentiary Hearing on Claim of Ineffective Assistance of Counsel in which claims of ineffectiveness of counsel are made.1

With regard to Applicant's motion it is noted that we have no allegation of ineffectiveness of counsel properly pending before us. Such must be presented to the trial court first and transmitted to this Court pursuant to Art. 11.07, supra.... That article requires all claims to first be presented to the trial court and, following a fact finding procedure conducted in that court, to be transferred to this Court. Since Applicant has failed to present these claims to the trial court, they are not properly before us at this time. Accordingly, we will dismiss Applicant's Motion to Continue Stay and Remand For an Evidentiary Hearing without prejudice to file the claim in the appropriate court.

Applicant's Motion is, therefore, dismissed without prejudice to file his application in the trial court pursuant to Art. 11.07, § 2, et seq., supra."

Graham's execution was set for August 17, 1993.

On July 21, 1993, Graham filed a civil suit in state court in Travis County against the Texas Board of Pardons and Paroles (TBPP) seeking an evidentiary hearing before that body on his request for clemency based on his claim of actual innocence. After a July 27, 1993, hearing, the Travis County state district judge, on August 9, 1993, issued a temporary injunction requiring the TBPP to hold a hearing on Graham's claim of innocence not later than August 10, 1993, or, in lieu thereof, to reschedule his execution until after such a hearing. The TBPP did not hold such a hearing, but instead filed a notice of appeal to the state court of appeals in Austin, which appeal operated to supersede the trial court's order. On August 13, 1993, the Austin Court of Appeals, on Graham's motion, enjoined his execution pending resolution of the TBPP's appeal to it. On August 16, 1993, the Court of Criminal Appeals, on Graham's motion, stayed his execution "pending further orders by the Court." On the same day, the Court of Criminal Appeals also denied motions, filed by the district attorney of Harris County and the TBPP, for leave to file with the Court of Criminal Appeals applications for mandamus to require the Austin Court of Appeals to vacate its injunction prohibiting Graham's execution. State ex rel Holmes v. Third Court of Appeals, 860 S.W.2d 873 (Tex.Crim.App.1993).

In the interim, Graham, through counsel, on July 22, 1993, filed his instant section 2254 petition with the district court below. The petition asserts only two grounds for relief: first, that Graham is actually innocent of the offense, so is entitled to relief under the opinions of five justices in Herrera v. Collins, 506 U.S. 390, 113 S. Ct. 853, 122 L. Ed. 2d 203 (1993), that "the execution of an innocent person would violate the Constitution"; and, second, that Graham was denied effective assistance of counsel, in that counsel failed to adequately investigate, particularly in failing to interview crime scene witnesses named in the police report, failed to investigate and present an alibi defense, failed to properly question witness Amos, and failed to call Hubbard as a witness.10 Graham also moved for an evidentiary hearing and for leave to undertake discovery.

Graham's petition was supported by numerous affidavits and exhibits. Much of this supporting matter consisted of material not previously submitted to the state courts. This "new" material included the following: (1) a July 10, 1993, affidavit of Sherian Etuk, who worked at the Safeway on the evening of May 13, 1981, and saw the shooting, or its immediate aftermath, described the perpetrator as a young black man not taller than 5'6"' having a very narrow face and light build, and declared she had been shown "photographs" by the police, was never contacted by anybody on behalf of Graham, and, examining four photographs of Graham ("one arrest photo, two ... in a line-up with other guys, and one ... dressed nice") stated "none of these photos depict the guy who shot the man out in the parking lot that night"; (2) May 25, 1993, affidavit of Leodis Wilkerson (age twelve in May 1981), who was present at the Safeway store with his aunt and cousins the evening of May 13, 1981, and witnessed the shooting, and was never contacted by anyone on Graham's behalf, describing the shooter as a short, young black man without a mustache11 (whose facial characteristics Wilkerson doesn't remember "that well anymore") and stating that of the three attached photographs of Graham (one in a line-up) "none of them to the best of my memory looks anything like the man who did the shooting at the Safeway"; (3) a May 1993 affidavit of Vanessa Ford tending to corroborate the alibi portions of Loraine Johnson's June 1, 1993, affidavit; (4) a June 1, 1993, affidavit of Loraine Johnson that gives essentially the same information as her April 18, 1993, affidavit (which had been before the state court), but adds more detail about her informing Graham's attorney, Mock, of the alibi; (5) a June 28, 1993, affidavit of Jo Carolyn Johnson that corroborates Loraine Johnson's affidavits as to Loraine informing Mock of the alibi witnesses; (6) Houston Police Department report on the offense;12 (7) July 1993 report of psychologist Loftus as to review of affidavits, statements, or testimony of witnesses to the offense (Amos, Hubbard, Etuk, Wilkerson, the Stephenses, and Skillern), concluding Skillern's identification of Graham was likely unreliable; (8) report dated April 20, 1993, of psychologist Willis, generally to the same effect as the above Loftus report, and stating, inter alia, "Bernadine Skillern's identification is totally lacking in reliability"; and (9) Houston Police Department Firearms Report of May 26, 1981, indicating the .22 caliber pistol Graham had with him when arrested was not the .22 caliber pistol with which Lambert was killed.

The state filed its answer and motion for summary judgment August 6, 1993, with supporting material, including an audio and video tape of an April 30, 1993, interview with Malcolm Stephens. The state's response waived exhaustion,13 and did not affirmatively raise the issue of successive or abusive petition under Rule 9(b) of the rules relating to section 2254 proceedings or state law procedural default. It did rely on the presumption of correctness of the state court findings under section 2254(d), but did not cite Keeney v. Tamayo-Reyes, 504 U.S. 1, 112 S. Ct. 1715, 118 L. Ed. 2d 318 (1992), or any of its progeny. That same day, Graham filed a seventeen-page response to the state's answer and motion for summary judgment.

On August 13, 1993, the district court, without any evidentiary hearing, rendered judgment dismissing Graham's petition. Graham v. Collins, 829 F. Supp. 204 (S.D.Tex.1993).14 Graham filed his notice of appeal the same day.

The district court initially noted that the state had waived exhaustion. Id. at 207. Then turning to Graham's claim of actual innocence, the court apparently interpreted Herrera to require a "threshold showing" that "based on proffered newly discovered evidence and the entire record before the jury that convicted him, no rational trier of fact could [find] proof of guilt beyond a reasonable doubt." Id. (internal quotation marks omitted). The court rejected Graham's claim, concluding he "has not met the 'extraordinarily high' threshold showing of actual innocence." Id. Next, the court rejected Graham's ineffective assistance of counsel claim. It noted that this was a successive claim that had been resolved against Graham in his first federal habeas, but that Graham could avoid the bar against a successive petition by making a colorable showing of factual innocence. The court observed that the affidavits of Etuk, Hubbard, West, and Amos "if credited, would satisfy" this requirement, and that "[t]he state court has determined that two of these affidavits are not credible." Id. at 208. The court went on to "assume arguendo that the evidence Graham has presented makes out a colorable showing of factual innocence," and accordingly considered the merits of Graham's ineffective assistance of counsel claim. Id. The court applied the section 2254(d) presumption of correctness to the state trial court's April 26, 1993, findings,15 and, concluding on that basis that neither defective performance nor prejudice had been shown, held that Graham's ineffective assistance of counsel claim was without merit. Id. at 208-09.

The scene now shifts back to the Texas courts, more particularly the judicial proceedings relating to the TBPP.

On April 20, 1994, after Graham's appeal herein had been fully briefed and argued, the Texas Court of Criminal Appeals granted writs of mandamus sought by the TBPP and the District Attorney of Harris County directing the Austin Court of Appeals to set aside its injunction, which had precluded Graham's execution pending resolution of the TBPP's appeal of the Travis County district court's temporary injunction. State ex rel Holmes v. Court of Appeals, 885 S.W.2d 389 (Tex.Crim.App.1994).16 Graham, through counsel, appeared before the Court of Criminal Appeals as the real party in interest. The Court held that the Austin Court of Appeals had no jurisdiction to enjoin Graham's execution. Id. at 393-396.17 The court went on to address the scope of Graham's available state habeas remedies in respect to his claim that evidence discovered since his conviction demonstrated his actual innocence. The court considered Herrera and its earlier opinion in Ex parte Binder, 660 S.W.2d 103 (Tex.Crim.App.1983). The court observed that in Binder it had held " 'post-conviction habeas corpus has not been and its not now the appropriate remedy for an applicant whose claim for relief is based on newly discovered evidence.' " Id. at 397 (quoting Binder at 106). The court then stated that "Graham contends that newly discovered evidence demonstrates his innocence of the crime for which he was condemned," that "[f]rom our reading of Herrera, we understand six members of the Supreme Court to have recognized the execution of an innocent person would violate the Due Process Clause" and that "[w]ith this sound and fundamental principle of jurisprudence we cannot disagree; such an execution would surely constitute a violation of a constitutional or fundamental right." Id. at 397. The Court went on to conclude "we hold that habeas corpus is an appropriate vehicle for Graham to assert his claim. To the extent that it conflicts with this holding, Binder is expressly overruled." Id. at 398. The Court proceeded to consider the standard under which a claim such as Graham's should be addressed in a Texas habeas context. It held in this respect as follows:

"... we hold an applicant seeking habeas relief based on a claim of factual innocence must, as a threshold, demonstrate that the newly discovered evidence, if true, creates a doubt as to the efficacy of the verdict sufficient to undermine confidence in the verdict and that it is probable that the verdict would be different. Once that threshold has been met the habeas court must afford the applicant a forum and opportunity to present his evidence." (Id. at 398).

....

"This threshold standard and burden of proof will satisfy the Due Process Clause of the Fourteenth Amendment and we adopt them in the habeas context. If the applicant meets the threshold standard announced above the habeas judge must hold a hearing to determine whether the newly discovered evidence, when considered in light of the entire record before the jury that convicted him, shows that no rational trier of fact could find proof of guilt beyond a reasonable doubt.

Therefore, we ... hold that, pursuant to Tex.Code Crim.Proc.Ann. art. 11.07, Graham may appropriately couch his claims of factual innocence in the context of a violation of the Due Process Clause of the Fourteenth Amendment." Id. at 399 (footnote call omitted).

Significantly, in a footnote appended to the last above quoted sentence, the Court stated:

"We note that in denying Graham's second application for writ of habeas corpus, we summarily overruled a similar claim based on the Due Process Clause of the Fourteenth Amendment to the United States Constitution. Graham, 853 S.W.2d at 565. We decide the issue today after extensive briefing by the parties and careful reconsideration of Graham's claim. Consequently, we believe our summary action was erroneous and Graham is not precluded from raising similar allegations in a subsequent writ application." Id. at 399 n. 13.

Finally, the Court declined to use the case then before it to itself then resolve Graham's claim, because "there is no [habeas] application presently pending before this Court, nor has the trial judge been given the opportunity to prepare findings of fact consistent with art. 11.07 § 3." Id. at 399. The Court observed, however, that "Graham is free to pursue his claims through the filing of an application under Tex.Code Crim.Proc.Ann. art. 11.07." Id.18

The Austin Court of Appeals on June 22, 1994, set aside the Travis County district court's temporary injunction against the TBPP, but did not rule on the merits of the controversy. Texas Bd. of Pardons and Paroles v. Graham, 878 S.W.2d 684 (Tex.App.Austin 1994). Thereafter, in October 1994 the Travis County district court rendered judgment that Graham was not entitled to a hearing before the TBPP on his clemency petition based on his actual innocence claim. Graham appealed, and on January 10, 1996, the Austin Court of Appeals affirmed. Graham v. Texas Board of Pardons and Paroles, 913 S.W.2d 745 (Tex.App.Austin, 1996; writ dism'd w.o.j.). The Austin Court of Appeals relied largely on the Court of Criminal Appeals' April 20, 1994, opinion in State ex rel Holmes, supra. The Austin Court of Appeals stated:

"Indeed, the protections afforded by the Texas Constitution may exceed those of the federal constitution even though the phrasing of a provision is the same or similar in both charters.... With this independent vitality of our state constitution in mind, we hold that the due course of law provision in the Texas Constitution guarantees Graham the right to a hearing on his claim of actual innocence. Our reasoning is much the same as that employed by the Court of Criminal Appeals in [State ex rel] Holmes: the execution of an innocent prisoner violates the constitution, and therefore a claim of actual innocence by a death-row prisoner based on newly discovered evidence merits a hearing. Holmes, 885 S.W.2d at 397-98. However, we determine that Graham's right to a due course of law hearing on his claim of actual innocence has been satisfied by the habeas corpus procedure fashioned for him by the Court of Criminal Appeals in Holmes. Upon a showing of new evidence that undermines confidence in the jury verdict, Graham will be entitled to an evidentiary hearing in accordance with statutory post-conviction habeas corpus procedures. Holmes, 885 S.W.2d at 398-99.... Now that the Court of Criminal Appeals in Holmes has created a judicial vehicle for testing such a claim of actual innocence, we hold that the Texas Constitution does not afford Graham an additional, duplicative hearing within the executive-clemency process." Graham, 913 S.W.2d at 751.

In his appeal to this Court, Graham reiterates his claims made below and asserts that the district court erred by denying his petition without any evidentiary hearing, that he was denied effective assistance of counsel, that Graham is innocent and under Herrera "[t]he inadequacy of the clemency 'fail-safe' requires this Court to intervene," and that the district court erred in granting summary judgment before the expiration of the ten-day notice period provided by Fed.R.Civ.Proc. 56(c). We do not reach the merits of these contentions, as we hold that Graham's habeas petition should be dismissed for failure to exhaust state remedies.

The exhaustion doctrine, generally codified in section 2254(b) & (c), requires that normally a state prisoner's entire federal habeas petition must be dismissed unless the prisoner's state remedies have been exhausted as to all claims raised in the federal petition. Rose v. Lundy, 455 U.S. 509, 102 S. Ct. 1198, 71 L. Ed. 2d 379 (1982). As the Court said in Rose:

"A rigorously enforced total exhaustion rule will encourage state prisoners to seek full relief first from the state courts, thus giving those courts the first opportunity to review all claims of constitutional error. As the number of prisoners who exhaust all of their federal claims increases, state courts may become increasingly familiar with and hospitable toward federal constitutional issues.... Equally as important, federal claims that have been fully exhausted in state courts will more often be accompanied by a complete factual record to aid the federal courts in their review." Id. at 518-19, 102 S.Ct. at 1203-4.

We have held that a habeas petitioner fails to exhaust state remedies when he presents material additional evidentiary support to the federal court that was not presented to the state court. See Joyner v. King, 786 F.2d 1317, 1320 (5th Cir.) (holding that the policies underlying the exhaustion doctrine require that "new factual allegations in support of a previously asserted legal theory" be first presented to the state court), cert. denied, 479 U.S. 1010, 107 S. Ct. 653, 93 L. Ed. 2d 708 (1986); Brown v. Estelle, 701 F.2d 494, 495-96 (5th Cir.1983) (holding that when a claim is filed in federal court in a significantly stronger evidentiary posture than it was before the state court, it must be dismissed for failure to exhaust state remedies). See also Barrientes v. Johnson, No. 95-40880, 96 F.3d 1441 (5th Cir. Aug. 20, 1996) (unpublished).

Graham, in support of his current section 2254 petition, has presented significant evidentiary support for his claims of actual innocence and ineffective assistance of counsel that was never presented to the state courts. Thus, he has not exhausted his state remedies.

Of course, exhaustion is not required if it would plainly be futile. "An exception [to the exhaustion requirement] is made only if there is no opportunity to obtain redress in state court or if the corrective process is so clearly deficient as to render futile any effort to obtain relief." Duckworth v. Serrano, 454 U.S. 1, 3, 102 S. Ct. 18, 19, 70 L. Ed. 2d 1 (1981).

As to Graham's ineffective assistance of counsel claim, the Court of Criminal Appeals in its per curiam order of July 5, 1993, denied Graham relief "without prejudice" to his first seeking relief in the trial court on the basis of his claims of newly-discovered evidence. Ex parte Graham, 853 S.W.2d at 571 & n. 1.19 Graham has not exercised that right, and it appears to be still available to him. Cf. Tex.Code Crim.Proc. Art. 11.071 § 5(a) (allowing successive claim if previously "the factual or legal basis for the claim was unavailable," or if it is shown "by a preponderance of the evidence, but for a violation of the United States Constitution no rational juror could have found the applicant guilty beyond a reasonable doubt," or if it is shown "by clear and convincing evidence, but for a violation of the United States Constitution no rational juror would have answered in the state's favor one or more of the [punishment] special issues"); § 5(e) (factual basis unavailable if "not ascertainable through the exercise of reasonable diligence").20

As to Graham's actual innocence claim, the Court of Criminal Appeals' April 20, 1994, decision holds that Graham's allegations in this respect state a constitutional claim, both under the United States Constitution (based on its reading of Herrera ) and under the Texas Constitution, each cognizable in a state court habeas proceeding, that, after "careful reconsideration of Graham's claim," its earlier action in which it "summarily overruled" Graham's said claim "was erroneous," and that "Graham is free to pursue his claims" through a subsequent state habeas corpus proceeding. State ex rel Holmes, 885 S.W.2d 389, 397-399 & n. 13. This seems to be a clear holding that state habeas relief is available to Graham with respect to this claim on a basis at least as favorable to him as he would have in federal court.21 To the same effect is the January 1966 opinion of the Austin Court of Appeals in Graham v. Texas Board of Pardons and Paroles, 913 S.W.2d at 751 ("on his claim of actual innocence ... upon a showing of new evidence that undermines confidence in the jury verdict, Graham will be entitled to an evidentiary hearing in accordance with statutory post-conviction habeas corpus procedures").

We are unable to conclude that resort by Graham to the state courts respecting either--much less both--of the claims raised in his instant petition would be futile.

Finally, we consider the effect of the state's waiver of exhaustion. Clearly, failure to exhaust is not a jurisdictional or inflexible bar to the grant of federal habeas relief to a state prisoner. Granberry v. Greer, 481 U.S. 129, 107 S. Ct. 1671, 95 L. Ed. 2d 119 (1987); McGee v. Estelle, 722 F.2d 1206 (5th Cir.1984) (en banc); Thompson v. Wainwright, 714 F.2d 1495 (11th Cir.1983). Just as clearly, however, federal courts, trial and appellate, are not obliged to accept a state's waiver of exhaustion, though ordinarily the waiver will be honored.22 As we said in McGee:

"A finding of waiver does not conclude our consideration, for a district court or a panel of this court may consider that it should not accept a waiver, express or implied. As the Eleventh Circuit observed in Thompson v. Wainwright [714 F.2d 1495; 1983], '[c]omity is not a one way street.... Strong federal interests may exist that, balanced against those of the state in the particular case, will permit the district court in its discretion to decline a waiver and require state exhaustion.' 714 F.2d at 1509. One of those interests is the burden on the federal system. Additionally, it may appear that state remedies would be effective, or that evidentiary development would be aided by requiring a hearing in state court.... Accordingly, we hold, as did the Eleventh Circuit in Thompson, that the district court, or a panel of this court, in its discretion may either accept or reject the state's waiver of the exhaustion requirement, or notice sua sponte the lack of exhaustion." Id. at 1214 (emphasis added; footnotes omitted).

Similarly, in Granberry the Supreme Court held that although exhaustion was a nonjurisdictional matter that could be waived if not raised by the state,23 nevertheless such a waiver did not preclude the appellate court from requiring exhaustion in a particular case in the exercise of its discretion.24 The court adopted "an intermediate approach" under which "the courts of appeals [are] to exercise discretion in each case to decide whether the administration of justice would be better served by insisting on exhaustion or by reaching the merits of the petition forthwith." Id. at 1673. Granberry gives the following example of a case in which the Court of Appeals might, sua sponte, require exhaustion, viz: "If, for example, the case presents an issue on which an unresolved question of fact or of state law might have an important bearing, both comity and judicial efficiency may make it appropriate for the court to insist on complete exhaustion to make sure that it may ultimately review the issue on a fully informed basis." Id. at 1675. As an example of a situation in which the appellate court might decline to sua sponte insist on exhaustion, Granberry posits the following: "Conversely, if a full trial has been held in the district court and it is evident that a miscarriage of justice has occurred, it may also be appropriate for the court of appeals to hold that the nonexhaustion defense has been waived in order to avoid unnecessary delay in granting relief that is plainly warranted." Id. at 1676.

The present case is one which fits the first Granberry example, not the second. The issues in this case are almost exclusively factual, and the relevant factual scenario is complex, highly controverted, and in many respects unresolved. The district court denied the petition without an evidentiary hearing. There is a large body of relevant evidence that has not been presented to the state court. It is doubtful that the record before us allows review of the underlying issues on a fully informed basis. Moreover, the state's reason for waiving exhaustion (see note 13)--so as not to "allow Graham to further politicize his case"--is questionable at best and has no legitimate relevance to what course of action would best serve the administration of justice. We conclude that in the circumstances of this case the due administration of justice would be significantly better served by insisting on exhaustion. For these reasons, in the exercise of our discretion, we decline to accept the state's waiver of the exhaustion requirement.

Graham has not exhausted his state remedies, and we have refused to accept the state's waiver of exhaustion. We accordingly vacate the district court's judgment and remand the case with directions that Graham's petition be dismissed without prejudice for failure to exhaust state remedies.

VACATED and REMANDED.