Is dishonesty sufficient to terminate a grad student?
Termination of the advising/mentoring relationship

You should check with your department or university policies, but at most places you can unilaterally terminate your advisory / mentoring role by emailing the department chair or graduate coordinator. This is, after all, a voluntary role for you. And given that you no longer trust the student, I don't think you can operate as their advisor in good faith yourself (you couldn't write the letters of recc that they'd need for funding or jobs, for example). 

If you don't feel the relationship can be repaired, then you should drop them. 

If the student has no other advisor, they may be at risk to be an orphan. Since most stages of graduate school (orals, candidacy, continuing enrollment, funding, research) require an advisor, a student who has no advisor is at risk of not being able to continue in the program. There is often a short period of time that is given to the student to find a new advisor. At some places students are formally terminated if they can't advance; at others not being allowed to advance puts them in a limbo state where they cannot enroll but are not terminated. 

Departments tend to not like the creation of orphans and there may be informal sanctions for an advisor who orphans students for no good reason. However, you do seem to have a good reason and if true, your colleagues should back you. 

The real result is however that the student may have to leave the program. 

University Expulsion

Not being able to continue for lack of an advisor is much more common than actual expulsion, given that expulsion procedures usually require a hearing and the presentation of proof of malfeasance.