Labour�s iron grip has been shaken off at local level � will the LibDems now join the SNP in a coalition to change the face of Holyrood, too?

I'm off to buy a hat in order to eat it." So said one prominent media face on Friday morning. When Alex Salmond announced two years ago that he was going to win 20 seats, everyone in the Scottish press, myself included, scoffed at the idea. Pah! The nationalists had come third behind the Liberal Democrats in the 2005 general election vote. "Alex will live to regret saying that," we said. Well, the hat shops of Scotland are doing brisk trade this weekend.

Let's be clear: this was a hugely significant, even revolutionary result. It is comparable to the Labour victory in 1997 which brought to an end the Conservative hegemony of British politics - except this election could have rather more profound implications for the British constitution.

Scotland now has a new political landscape. Gaining 20 Holyrood seats was, of course, remarkable enough, given the dominance of Labour in West Central Scotland and the hostility of the popular media, which tried to hijack the election by vilifying Alex Salmond. The Sun should be ashamed of its polling day front page depicting a hangman's noose as the penalty for voting SNP. This time, it was The Sun wot really lost it But look at the councils of Scotland. Labour have been reduced to just two: Glasgow and Lanarkshire. The SNP have returned 360 councillors, 100 more than their target. This means that the Labour monolith, which has run Scotland from the bottom up, is now being dismantled from the top down. In future, in all those councils which were Labour one-party states there is now a series of coalitions in which the SNP and the Liberal Democrats, where not actually in office, will provide vigorous oppositions.

The new cohorts of non-Labour councillors represent the seed-corn of the political future. They will be working to challenge Labour's hegemony of the local state, of public appointments, of the local media. Scotland is now two countries: West Central Scotland and The Rest. But even in Labour's heartland, in its western fortresses, there is now an SNP presence.

Five nationalist MSPs in Glasgow, for heaven's sake. Plenty of the voters of the west may have responded to the command of the popular tabloids this time around, but they may not do so readily in future once non-Labour politicians are no longer aliens in the west.

Of course, for the revolution to be realised, the SNP must form a government. This will have to be cemented within the week, and the only realistic, democratically credible solution is a coalition between the SNP, the Liberal Democrats and the Greens. They have the numbers (the crucial 65 seats); they have the policies (anti-Trident, local income tax, nuclear power, fiscal autonomy), and they have the "moral authority" - a phrase that Alex Salmond has astutely inserted into the post-election political discourse.

And such a coalition would also have the only credible leader in the Scotland. Alex Salmond has proved in this historic campaign that he has earned the right to be the next first minister. It is very difficult to see how Jack McConnell could continue to lead Scotland from the back after his party's dismal outing - read the devastating comments on the Labour leader from his own campaign team in today's Sunday Herald.

Nicol Stephen, the Scottish Liberal Democrat leader, also had a poor campaign. He failed to connect with the electorate; lost two key MSPs in Euan Robson and George Lyon, and shed thousands of votes from his own majority. If McConnell and Stephen's political overlords - Gordon Brown, and Menzies Campbell - believe the Holyrood pair can cling on to power, with a kind of rump Lib-Lab administration backed by the Tories, they are deluding themselves.

The people of Scotland would not stand for two parties given such an electoral pasting attempt to form a coalition of the rejected. Such a Scottish Executive would lack any kind of authority at all, moral or otherwise. It would confirm the worst paranoid fears of Scots that Holyrood was actually run by London. McConnell would appear as a puppet and Stephen as a muppet.

Of course, the Liberal Democrats don't want to do a deal with Alex Salmond. They don't trust the SNP leader, think he's a demagogue who would not listen to them and would run the Scottish Executive as if it were his fan club. But the LibDems may not be in a position to refuse to do a deal. The logic of proportional democracy, and their own pronouncements on the need for stable coalition government in Holyrood, may ultimately force them into a coalition. It has to be with the SNP because there is simply no reasonable democratic alternative. The people have spoken - and the MSPs have their ministerial careers to think of, too.

What these two parties should do is park the referendum issue in a constitutional convention for the duration of this parliament. The SNP and the LibDems have both talked favourably about setting up such a body to review Scotland's future relationship with the UK; its powers and responsibilities, its financing and taxation.

They should call on all interested parties to join this convention and allow it to do its work, as did the 1988 Scottish Constitutional Convention, which drew up the blueprint for devolution. Let this issue be taken out of the day-to-day running of the parliament, and allow Scotland's government to be stabilised.

By all means let the LibDems continue to say they don't want a referendum, and let the SNP say they do want one - but farm out the whole debate to the constitutional convention. It should decide how and when the Scottish people should be consulted after it has deliberated. I believe that the SNP would agree to do this, and would even accept a multi-option referendum at the end of it, including the LibDems' option of federalism, ie,s a devolved parliament with enhanced powers.

The alternative for the SNP is that their bill for a referendum, if they put it to the parliament as piece of minority legislation, would be resoundingly defeated. So what have the Nats to lose by taking on the idea of a constitutional convention? Gordon Brown may try to prevent Labour taking part, but that would possibly split the Scottish Labour Party - I have spoken to members of the party who would willingly participate. If Ming Campbell orders the LibDems to stay out, they would split.

Taking the referendum out of the equation would allow a Nat-Lib Dem-Green coalition to honour its democratic covenant with the voters and prepare a programme for government. And that programme practically writes itself: the LibDems and the SNP are agreed on the need to scrap the council tax and introduce local income tax; to lower business taxes, establish a growth target for Scotland and promote enterprise. They are both for renewable energy, against nuclear power and Trident and in favour of liberal policies on asylum and immigration. They want more police on the streets, more teachers in schools, smaller class sizes and to maintain local hospitals.

On crime, they agree on community sentencing, police reform and longer sentences for knife crimes. They want affordable housing, promotion of wave and tidal power, carbon emission targets and implementation of the National Gaelic plan. I can also reveal exclusively that Alex Salmond would not object to Nicol Stephen's No 1 legislative priority - an hour of physical education a day in schools - just so long as it doesn't apply to him.

There is such an obvious fit between the policies of these two parties that it seems almost absurd that they are not able to do a deal, and a failure to do so would not go unnoticed by the people of Scotland. The Greens would certainly support this coalition, especially if Robin Harper were to be given an environmental brief, and even Margo MacDonald, the last of the independents, may be tempted to join in.

What Labour might ask the LibDems to do, given that the option of a continuation of the Lib-Lab coalition is not credible, is to retreat to the backbenches, let the SNP run a minority administration and join Labour MSPs in a guerrilla war against Alex Salmond. They could try to frustrate the effective operation of the Scottish Executive, and hope that the civil servants would also sit on their hands and do nothing to assist the nationalists in running an effective administration.

Well, the LibDems would be entitled to do that, certainly. There is nothing in the rule book that says they have to join a coalition, just as there is no rule that the largest party in the Scottish election should necessarily lead a coalition. But Nicol Stephen would do well to note his own parlous state after this election, where the Liberal Democrats came fourth after the Conservatives. The only way to salvage something from the mess is to try to remain in government and exert some influence on events.

The Liberal Democrats have to ask themselves whether they really want abandon their ministerial posts and their policies just so they could prove that the Scottish people had voted in the "wrong" way on May 3. But the people might not be very forgiving.

The LibDems should observe how the SNP won this election against the determined opposition of the pro-Labour establishment in Scotland. They might then consider whether boycotting the new Scottish Executive might exclude them from relevance to the new political Scotland, and the emerging Scottish consensus on the need for greater autonomy for the Scottish parliament. Might it not be better for the LibDems to get in there and stake their claim, rather than appear to go down with Labour?

After all, where have Labour been for the last 48 hours? They ceded the media, and the political initiative, entirely to Alex Salmond, right from the moment when the nationalist leader, after helicoptering into Edinburgh like a president-elect, cheekily delivered his victory speech even before he had won the election. Was it a media coup, or a constitutional coup d'etat?

Where was Jack McConnell? If Labour were so convinced of their own moral authority to govern, why did the first minister not come out to present his case to the nation on Friday? Why did he not condemn Salmond for hijacking the election, pre-empting the nation and assuming the mantle of leadership? I spent much of the immediate post-election period with the international media encampment outside Holyrood. The SNP were there in strength throughout, but of Labour there was little sign. Ministers, from McConnell down, simply hid from the cameras because they didn't know what to say.

More to the point, where has Gordon Brown, the architect of Labour's campaign, been when his party and country needed him? Playing Macavity The Mystery Cat, pretending not to be there when things went wrong? Leaving it to Tony Blair, of all people, to field the questions on the situation in Scotland, when it was the chancellor who should have been taking to the airwaves to make the case for a united Britain.

The Labour establishment in Scotland failed to get its post-election act together and it is important to ask why. Was it for the same reason the campaign was misconceived from the start? Was it because of the cynical arrogance of ministers who believed Scots voters could be scared into line by a relentlessly negative campaign expressed in the rebarbative rhetoric of The Sun?

A lot of people in Scotland this weekend have discovered to their surprise that they were closet nationalists. Friends of mine, including long-time Labour supporters, talk of being astonished by their own elation at the result of this election. There is an unmistakable air of excitement, even optimism, which has largely blown away the embarrassment at the computerised chaos of the count. Scotland doesn't often feel this way. Beware: it might be habit-forming.