Mr Kuchma has resisted demands to resign

Mr Kuchma is coming under increasing pressure to resign over his alleged involvement in last year's killing of a journalist, Georgiy Gongadze, who specialised in writing about corruption in high places.

Flying into the eastern city of Dnipropetrovsk, Mr Putin said: "Regardless of the complex political situation, we will work with the president elected by the Ukrainian people."

The BBC's Robert Parsons in Kiev says it is a measure of the importance Russia attaches to its relationship with Ukraine that Monday's meeting was the eighth between the two leaders since Mr Putin came to power a year ago.

We love Russia! If we stay together everything will be fine!

Workers at the Yuzhmash missile factory

He says Mr Putin must realise that Russia has an opportunity now to draw Ukraine back into its fold.

At their last meeting, in December, the two leaders signed a schedule for Ukraine to repay its gas debts of between $1.4bn and $2bn.

After Monday's meeting Mr Kuchma described the deal on electricity as a "colossal step".

The two leaders also signed a deal on destroying leftover booster rockets from Soviet-era nuclear missiles.

Gongadze crisis

16 September: Gongadze disappears 2 November: Headless body found 28 November: Kuchma tapes made public 10 January 2001: Body identified by DNA tests 6 February: Demonstrations escalate 10 February: Kuchma sacks head bodyguard and security chief

As they walked past rockets and spacecraft at the Yuzhmash missile factory workers shouled out: "We love Russia! If we stay together everything will be fine!"

Mr Putin answered: "We have come exactly for that and reached important agreements."

As they met, demonstrators in Kiev were staging their third mass protest in a week, calling for Mr Kuchma's resignation.

The Ukraine Without Kuchma movement, which is organising opposition to the president, says Mr Kuchma's voice can be heard on a tape saying he wants to be rid of Mr Gongadze.

Mr Kuchma has acknowledged that it is his voice on the tape, which was obtained when his office was bugged by a bodyguard, but claims that it has been edited to change what he said.

On Saturday, Mr Kuchma sacked the head of the security service, Leonid Derkach, and the chief of the presidential bodyguard, Volodymyr Shepel.

Though the Ukrainian economy grew last year, opposition to Mr Kuchma is fuelled by poor living conditions resulting from a decade of economic decline.