# Matching Algorithm in Graph Theory

Given $n$ people, $k$ out of which own a car. We need to match a car for each person without a car. Conditions:

• Each car fits $5$ people, including the driver.
• Each driver will only allow his friends to ride with him.

I am looking for an algorithm to determine if there is a match. i.e. everyone gets to ride.

I am not seeking complete answer. Hints/pointers should suffice since this is part of my college assignment.

Thank you.

This might be an extension of the marriage theorem, except that any group of n passengers needs to be friends with at least $\left \lceil \frac{n}{4}\right \rceil$ drivers.