The return to power of Avigdor Lieberman and his anti-Arab racism is a mark of the point Israeli politics has now reached

At one level you have to hand it to the Israelis. Once cleared into the Knesset, the parliament building, journalists can wander into the members' cafeteria without an escort. Cheaply made tables are packed together as closely as in an airport terminal, and ministers queue to load their trays with no priority over backbenchers. Avigdor Lieberman, the ultra-rightwinger, hunches over a soup bowl by the window. Two tables away Ahmed Tibi, an Arab who is deputy speaker, chats to reporters in between fielding mobile phone calls. It is admirably egalitarian and unstuffy, but the mood was far from relaxed on Monday. The government majority was just about to vote to approve Ehud Olmert's appointment of Lieberman as deputy prime minister, with a brief to handle the "strategic threats" which Israel faces.

Tibi was furious. In other parts of the world a man like Lieberman - "a very dangerous and sophisticated politician who has won his support through race hatred" - would be shunned, he fulminated. In Israel he was given a top job.

Lieberman has described Tibi and other Israeli Arabs who have met Hamas officials as traitors. They should be executed, he said last year, just as the judges at Nuremberg condemned not only Nazi leaders but those who collaborated with them. Lieberman also advocates stripping Arabs in north-eastern Israel of their citizenship and putting their areas under Palestinian rule. In return, Israel should take more land on the West Bank than even Olmert envisages.

Tibi was not worried that the government "would become more brutal" because of Lieberman's presence in cabinet. After all, the mushrooming of roadblocks in the West Bank, the assassinations in Gaza and the war on Lebanon happened without him. "Our problem is with Israeli society," said Tibi. "The appointment of this racist and fascist sends a message to me as an Arab and a human being."

Sitting in the cafeteria alongside Tibi, Zehava Galon, who leads the parliamentary wing of Meretz, Israel's small leftwing party, was equally appalled. Her anger was directed at the Labour party ministers in Olmert's coalition for failing to resign in protest. This was bound to lower politicians' public respect by several more notches, she said. She had written a letter to the Labour caucus arguing that Lieberman was worse than Austria's Joerg Haider or France's Jean-Marie Le Pen. But only one minister chose to leave the government.

"Lieberman's appointment will influence the whole atmosphere of Israeli society," said Galon. "Ministers are only interested in keeping their chairs ... Politicians are already seen as cynical, with no values, no ideology, no principles. This will make it worse. There is no leftwing camp in Israel now. If the Labour party thinks it's legitimate to be allied with Lieberman, I can no longer consider them left, liberal or democratic. This appointment is a terrorist attack on democracy."

As her gloom and anger mounted, the man himself carried on lunching, pausing only to take a few questions from the Guardian. In a mixture of Russian and English, he told me that his priorities in government would be "to establish a proper process of decision-making" and push through "a strategic vision for the final solution of how Israel will look in 20 or 25 years' time ... It's not only an issue of territory and borders but of the character of the state - will it be a Zionist state, a Jewish state, or a state like others? I want it to be a Jewish state."

Labour ministers acknowledge that their support was crumbling before the Lieberman appointment. Amir Peretz, their party leader, currently has a poll rating as a potential prime minister of a derisory 1%. He is one of the first defence ministers with no military background - "the only things which have ever whistled past him are ping pong balls", as one opponent sneered. He was widely criticised for his performance in the Lebanon war. Meanwhile, Labour's promises to use its role in government to protect spending on social services came to little. The latest budget lifts military spending even higher.

Nevertheless, it was better to stay in the cabinet, since Lieberman was only one of 25 ministers, maintained Yuli Tamir, the education minister. Lieberman's role was defined narrowly. He was not in charge of defence or foreign policy, and had no spending powers.

Given the public's disillusionment with politicians, wouldn't it raise Labour's standing to resign, I asked. "It'll go up for a moment, but resigning is only popular for a while," replied Tamir. "Besides, we thought Lieberman would have more power if we pulled out."

While Labour's critics call the party's bigwigs cynical for clinging to their cabinet seats, no one overlooks the cynicism of Olmert and Lieberman. By bringing Lieberman into the cabinet, Olmert has given his unstable coalition a sudden new burst of life. Struggling after the fiasco of the war in Lebanon, he now has 78 votes in the 120-seat Knesset and is safe from being toppled.

Lieberman's motives are also clear. A protege of the former Likud prime minister Bibi Netanyahu, he formed his own party after Netanyahu lost power in 1999. He got his initial support from post-Soviet Russian immigrants, appealing to their anti-Arab racism and instinct for tough leadership. Taking his cue from Vladimir Putin in the Kremlin, Lieberman advocates raising the threshold for small parties to get into parliament, thereby effectively shutting the Arab ones out.

Recently he has sought to broaden his political base and, since Lebanon, polls have shown him with twice as much support as Olmert, though still not as much as his old mentor, Netanyahu, who tops the current rankings. Joining Olmert's government allows him to get a different profile from Netanyahu. It also gives him a chance to pull Olmert in a hardline direction and take credit for it at the next election.

Lieberman has been in government before. He served twice under Sharon, but was sacked for his "population swap" ideas and for opposing the disengagement from Gaza. The fact that Sharon's successor has brought him back, this time as a deputy prime minister, shows how far to the right Israel's policy makers have moved, even as progressive Israelis feel increasingly sickened by the musical chairs at the top. Recent corruption and sex scandals had already tarnished the image of the political class. Now people wonder which is worse: Lieberman coming in or Labour not going out.