This is not the same as Rudra stabbing Prajapati at the request of the other Gods for his incest with his daughter.
Chapter 8, Vidyeswara Samhita of Shiva Mahapurana says Shiva created "Kala Bhairava" from his eyebrows to behead Brahma when Brahma lied about top of infinite Linga. Bhairava is nothing but Lord Shiva as described in this answer (translated by Shantilal Nagar)
ससर्जाथ महादेवः पुरुषं कञ्चिदद्भुतम्।
भैरवाख्यं ध्रुवोर्मध्याद्ब्रह्मदर्पजिघांसया। १॥
Nandi said: Thereafter, Šiva, in order to shatter the pride of Brahma, produced an astonishing type of a person from out of his eyebrows.
स वै तदा तत्र पतिं प्रणम्य शिवमङ्गणे।
किं कार्यं करवाण्यत्र शीघ्रमाज्ञापय प्रभो!।। २॥
Soon after his emerging, he offered his salutation to lord Siva in the battle ground itself and asked him, “O Lord, what have I to do? You kindly get me the command at once.”
वत्स योऽयं विधिः साक्षाञ्जगतामाद्यदैवतम्।
नूनमर्चय खड्गं स्वं तिग्मेन जवसा परम्।। ३।।
Siva said, “O Bhairava, you better, adore Brahma, the primeval lord of the earth, with a sharp edged Sword (or kill him)'.
स वै गृहीत्वैककरेण केशंतत्पञ्चमं दृप्तमसत्यभाषिणम्।
छित्वा शिरो हास्य निहन्तुमुद्यतः प्रकम्पयन्खड्गमतिस्फुटं करैः।। ४।
On hearing this Rudra caught hold of the hair of Brahma's head in his hand, and severed his fifth head which told the untruth and got ready to kill him.
Also, Chapter 35, Rudra Samhita (Sati Khanda) of Shiva Mahapurana says Kalabhairava of Kashi cut the head of Brahma.
श्रीकालभैरव: काश्यां नखाग्रेणौव लीलया।
पुरा शिरश्च चिच्छेद पञ्चमं ब्रह्मणो ध्रुवम्॥५२।।
Kalabhairava at Kasi had cut off Brahma's head even by Scratching with the nails.
Chapter 14, Uttaraardha Arunachala Mahatmya of Skanda Purana gives different narrative here which could be due to Kalpa Bheda and it says Shiva banished Brahma's worship when he lied he saw top of Linga.
I have heard from learned persons, the answer as follows: Lord Shiva marries Maa. Parvathi. Lord Brahma conducts the marriage as the main priest. After the marriage, Shiva was very happy and wanted to give a gift to Brahma. Shiva asks Brahma to make his wish. Brahma with 5 heads at that time was very high headed and wanted to insult Shiva. He tells Shiva that whatever Shiva wants to give him, he shall have to give him in a direction which is not seen by by him. Brahma having 5 heads, is looking in every direction! Shiva gets angry on Brahma for insulting him. Shiva snaps one head of Brahma from his finger nails.As Brahma is a Brahman, Shiva gets Brahma-hatya-dosha and the Brahma-kapala(Brahma's head) gets stuck in his hand. Any effort from Shiva to get rid of Brahma-kapala was in vain. then Lord Vishnu suggests that he shall go begging from person to person. Whose so ever Bhiksha(alm) fills the Brahma-kapala, it will fall off from Shiva's hand. Shiva goes on begging from person to person in all 3 Lokas. Nobody was able to fill the Brahma-kapala. Frustrated, Shiva begs his consort Parvathi for Bhiksha. She fills it with food. Immediately, the Brahma-kapala snaps from Shivas hand and falls down. Parvathi becomes Annapoorneshwari, providing food for the universe. This is how the story goes.