Private Catholic school. Of course it's legal. If it were an issue for your kid, your kid wouldn't be in that school. I would dare say some parents choose schools such as this BECAUSE of rules like this.
Now wait. I don't care if it is Catholic, private, Christian- whatever. To make a kid have a date in order to go to the prom is ridiculous. And this has NOTHING to do with sexual orientation in my book. Not all teens are even ready to "date". My DS is a senior, and has a steady girlfriend, but many of his friends are going alone to prom this year. They should be allowed to do so- I don't care what kind of school they go to. So yes, if my kid were in private school, and wanted to go stag to the prom, I would fight the rule for him. I might not win, but I would make his voice heard!