The following is a partial transcript of the Dec. 3, 2006, edition of "FOX News Sunday With Chris Wallace":

"FOX NEWS SUNDAY" HOST CHRIS WALLACE: We're joined by two key senators: Democrat Joe Biden, incoming chairman of the Foreign Relations Committee, and Republican Lindsey Graham of the Armed Services Committee. Both come to us today from their home states.

Let's start, if we can, gentlemen, with the Rumsfeld memo.

Senator Biden, what do you make of the recommendations and of the fact that at the same time the president was attacking Democrats for, as he said it, trying to cut and run, the defense secretary was at least raising the same idea?

SEN. JOE BIDEN, D-DEL.: Well, there was a clear disconnect between what the administration's been saying the last year and what's been going on on the ground. And the Rumsfeld memo makes it quite clear that one of the greatest concerns is the political fallout from changing course here in the United States politically and how to deal with that.

But the bottom line is there is no one, including the former secretary, who thought the policy the president continues to pursue makes any sense.

WALLACE: Senator Graham, whether it's the Rumsfeld memo or this very critical memo that came out this week from National Security Advisor Stephen Hadley about Iraqi Prime Minister Maliki, are you concerned about, as Senator Biden put it, the disconnect, the difference between what the administration has been saying in public and what it's apparently been thinking in private?

SEN. LINDSEY GRAHAM, R-S.C.: Yes, very much so.

You know, Democrats weren't the only people attacked. I've been saying for quite a while that the current strategy is not working.

My problem with the memo is that he suggests that the political leadership in this country lowered expectations.

My suggestion is that the political leadership, led by the president, needs to tell the American public a failed state in Iraq is a dramatic loss in the War on Terror. And we need to reconnect the outcome in Iraq to the overall war on terror. And that's what I think has been lacking.

WALLACE: Well, let's look forward to this bipartisan Iraq Study Group that's going to issue its recommendations on Wednesday. As both of you know, a number of those recommendations have already leaked out, including the basic idea of pulling U.S. combat troops out by 2008, dependent on conditions on the ground.

Senator Biden, is that too much of a timeline or too little?

BIDEN: I think it's the right timeline. It's what I put forward in my proposal, which you interviewed me on about six months ago, Chris, four months ago, because it recognizes the reality: that, by the end of 2008, one of two things is going to have happened.

We will either help broker a political settlement where the violence is abated in that country and/or things will be totally out of control. In either circumstance, we'll be in a position where we will not be either able to keep as many troops and/or want to keep as many troops.

WALLACE: Senator Graham, do you favor this idea? Is that about right, the idea of pulling U.S. combat troops out dependent on conditions on the ground by early 2008?

GRAHAM: I reject any proposal coming out of the Congress, any commission, the Pentagon or any other source that sets a deadline or a timeline.

To sum it up, my whole view of Iraq is based on how the outcome affects the overall war on terror. I believe it is the central battlefront in the war on terror.

The Islamic fascists that we're fighting in the War on Terror have several goals: to drive us out of the region, not just Iraq. So if you redeploy to a friendly country, they're coming after us in that friendly country because they want us to leave the region. They want to tackle all moderate regimes, all regimes that are unfaithful to their view of religion. They want to replace these regimes with religious theocracies that have a very dark view of humanity. And finally, they want to destroy the state of Israel.

We must stay, fight and win in Iraq. I reject timetables.

WALLACE: Well, so far at least, Senator Graham, President Bush seems to agree with you, because he seems, at least in public, not to be embracing the leaked recommendations of the Iraq Study Group.

Here's what he said after his meeting this week with Iraqi Prime Minister Maliki. Take a look.

(BEGIN VIDEO CLIP)

BUSH: This business about a graceful exit just simply has no realism to it at all. We're going to help this government.

(END VIDEO CLIP)

WALLACE: Senator Graham, what do you think the president should do? How should he handle and respond to the recommendations of the Iraq Study Group?

GRAHAM: We need to respond to the agenda of our enemy.

If we redeploy to a friendly nation under these circumstances, the terrorists will see that as retreat and defeat, and they will come after us in that friendly nation. They will say, "A ha, we've got them to break and leave in Iraq. They've gone to this new country. They think they're safe. Well, we're going to show America you're not safe. If you want to be safe, America, leave the region to us. Let us have our way in this region. If you want to be safe, give us Israel."

That's their agenda. So we've got to win in Iraq.

And any strategy that unites the country and we lose I'm against. I'd rather be divided as a nation and win than united and lose.

This is, to me, the central battlefront in the War on Terror. We need more troops, not less. The Iraqi people need some breathing space from this violence. We've screwed this war up in many ways. You can't have a democracy with this level of violence. When you have a high crime area, Chris, you don't send less police, you send more. We need more troops in Iraq, in the short-term anyway.

WALLACE: Senator Biden?

BIDEN: Well, look, I think that Lindsey makes a lot of good points, but the bottom line here is none of this is going to be doable unless there's a political settlement within Iraq.

You know, if, in fact, every jihadist in the world was killed tomorrow, we still have a major war in Iraq. And it's a sectarian war.

I have the constitution here in front of me, the Iraqi constitution, Chris. Everybody thinks I'm talking about dividing up Iraq. The fact of the matter is Article 120 of the constitution says that "federal authority shall have the right to exercise executive legislation." It goes on, "particularly to establish and organize internal security forces."

Let me put it to you another way. Does Lindsey or anybody else think in our lifetime you're going to see a Kurdish security force wandering around any of the cities in the Shia region? Does anybody think you're going to have Shia police or Shia military anywhere in a Sunni region?

We've got to get straight here. You've got to give the Sunnis buy-in and give them a piece of the oil, as they were promised in their constitution. You've got to give the people in the Shia regions the same kind of regional autonomy you gave the Kurds, with a loose federal government, like their constitution calls for.

It's a political problem.

In the meantime, we have to have forces there, I agree. And we've have passed the point, though, where we could put in the number of forces that could fundamentally change things. I called for that 2 1/2 years ago, to add 100,000 forces. My friend John McCain and others who are calling for it now said I was being hysterical. We had a chance to stabilize then. We don't have it now without a political solution.

And Lindsey is right. Just moving out without a political solution internally will result in the same thing he suggested. But you need a political solution. And Maliki I'm not sure is the guy that can carry the sleigh.

WALLACE: Let me move — well, I want to pick up on that for just a second, if I can.

GRAHAM: Could I comment on that?

WALLACE: Yes, you can respond to that, Senator, but let me ask you a question. Are we stuck with Maliki, Senator Graham?

GRAHAM: We're stuck with the elected representative of the Iraqi people. This man was chosen through a democratic process, which is sort of unusual for the region. And he's got more than he can handle. The troops on the ground have more than they can handle.

Joe has been pushing for more troops. I disagree with Joe in this regard: We still can turn this thing around.

When we talk about taking troops out, we deflate moderation and we embolden extremism. We have to boldly stand with the forces of moderation.

Maliki is a force of moderation, even though he's not done it perfectly. And we have to stand firmly against the forces of extremism.

We need a better security apparatus. No prime minister in Iraq can bring about democracy with this level of violence. No military commander can fight the insurgency, train the troops, and rebuild the police with this level of violence. The police force has to be rebuilt from the bottom up.

So when you set timetables and deadlines, you're really defeating, in my opinion, getting this right, because you deflate moderation and you embolden extremists.

We need more troops, with no deadlines.

WALLACE: Gentlemen, I want to switch to a related subject. The nomination of Robert Gates to be the new defense secretary comes up this week.

Senator Biden, you voted against Gates back when Bush 41 nominated him to be CIA director. Is the fact that he is not Donald Rumsfeld enough to make you vote for him this time?

BIDEN: When I voted against him, I said at the time it was a close call. I voted against him because there was a question of whether he hid information from the Iran-Contra commission, on the whole Iran-Contra affair.

I think Gates's position on Iraq is much closer to what we need to move to. I will vote for Gates, and I believe Gates will be able to do a good job.

WALLACE: Briefly, Senator Graham, why do you think that Bob Gates will do a better job on Iraq than Don Rumsfeld did?

GRAHAM: Because he has a chance to start over with the American public. He has a chance to produce new ideas. He's not a stakeholder in past mistakes as Secretary Rumsfeld was. He has a chance to re- engage.

I intend to vote for him unless he convinces me that he will not support a strategy to win. I'm looking for strategies to win, not political strategies.

WALLACE: Let me switch, if I can, to one last subject. We've had this real-life spy thriller, Russian spy thriller, playing out this week with the radiation poisoning of former Russian spy Alexander Litvinenko.

Question, and I'll start with you, Senator Biden: Do you believe — I understand it's speculation, but do you believe that Vladimir Putin, the Russian president, is involved? And whether we can prove that or not, how should it affect our relations with Russia?

BIDEN: Well, I don't know whether he's involved, but our relations with Russia have to get straightened out to begin with.

Russia is moving more and more toward an oligarchy here. Putin is consolidating power. He's been doing it for the last six years. We have basically been giving him a bye. I think that Russia is sliding further away from genuine democracy and a free-market system and more toward a command economy and the control of a single man.

So I'm not a big fan of Putin's, and I think we should have a direct confrontation with Putin politically about the need for him to change his course of action.

WALLACE: When you say — and very briefly, sir...

BIDEN: In Russia.

WALLACE: Let me say, when you talk about a direct confrontation, Senator Biden, would you expel him from the G-8 industrial summit?

BIDEN: Well, no, but I tell you what: I would consider laying down markers about whether or not, as he continues to consolidate power within that economy and in that country, whether or not he warrants continued membership. I would raise it.

And I would do it privately. I wouldn't make this a public confrontation.

WALLACE: And, Senator...

BIDEN: But I'd make it a direct — sorry.

WALLACE: No, no, I was just going to bring in Senator Graham.

In the time left, your thoughts about Putin and what the U.S. needs to do?

GRAHAM: I think Joe is right on. I think Bush misread his soul. I think this guy is taking Russia backward. He's a problem, not a solution, to most of the world's problems. He could help us with Iran if he chose to. He is becoming basically a one-man dictatorship in Russia. And we need to be tough with him.

Russia needs to be part of the international community in a constructive way. They're going backward, not forward. And now's the time for the international community to speak with Russia with one voice: "Change what's going on in Russia. Help us with Iran."

WALLACE: Senator Graham, Senator Biden, I want to thank you both for coming in and sharing part of your Sunday with us.

BIDEN: Thank you very much.

GRAHAM: Thank you.