на работе всех сотрудников хотят проверить на полиграфе. Насколько это законно, могут после этого уволить?

Это НЕ ЗАКОННО,, ,
- Поскольку полиграф назван средством оперативно-розыскной деятельности, работу с ним могут проводить только государственные служащие. Ни о каком тестировании при приеме на работу и речи быть не может, если, конечно, речь не идет о приеме на работу в разведчики. Отказ в приеме на работу по показанием полиграфа незаконен и может быть обжалован в суде.
- Если человек поставлен перед выбором – либо обследование, либо его заявление даже не рассматривается, то согласие на тест трудно назвать добровольным. Хотя, россияне, увы, пока в правовом смысле весьма безграмотны.

1)проверить могут хоть на чём
2)уволить по этому основанию не могут, нету статьи Обман работодателя или Дурные мысли против работодателя.. .
3)все вопросы решаются в письменной форме. если вам что не нравится - пишете им письмо (заказное с уведомлением) и задаёте любой идиотский вопрос: я не понимаю.. .
4)в суде работник должен доказать 2 факта - факт работы на данного работодателя и факт именно такой зарплаты. собирайте доказательства, лучше подлинники, можно и диктофонные записи разговоров с начальником, любые фото и т. п.

нет такого основания для увольнения - по показаниям полиграфа.

Незаконно, но в нашей стране можно все.
Особенно если у вас "белая" зарплата значительно ниже реальной.
Вас могут даже не увольнять, а оставить только "белую" часть и вы сами уйдете.
И сделать это могут и по результатам полиграфа и после отказа на нем тестироваться.
С другой стороны, если у вас вся зарплата белая, и на работу вы не опаздываете/прогуливаете, то уволить вас насильно практически невозможно, даже если вы на работе балду пинаете, восстановитесь по суду и дальше будете балду пинать, можете на эту тему почитать форумы сотрудников HR для них часто большой головняк избавится от ненужного, но нахального сотрудника.

Это незаконно. А уволить могут, так или иначе. Сами понимаете: "Не ту страну назвали Гондурасом".