Ttykuu

I have 18 students in my graph theory course this semester: Anne, Bernard, Clare, David,..., and Rachel. At the start of the course I asked them to draw the graph below, in which each of them is represented by a vertex, two of which are joined by a line if, and only if, they represent two students who are friends.

Fewer than half my students turned up for class last Friday. However, because each of the absent students happened to be friends with at least one of those who did attend, I was able to return everyone's assignments either personally or through a friend. In fact, had a smaller group of students shown up for my class on Friday, I would have been unable to do this.

How may students attended my class on Friday, and who were they?

This is an excellent question to demonstrate why the greedy algorithm doesn't always work

The minimum number is actually

$4$

Here are the students which would satisfy the criteria (I think this group is unique)

$F, J, N, O$ (Frank, Jack, Norman, Orville)

Proof that this is minimal

As El-Guest pointed out the maximum number of friendships in the group are held by $M$ & $E$ with $6$ & $5$, respectively. Every other person has four friends or fewer. Therefore, the maximum possible number of people covered by three students is $7+6+5 = 18$. This could only possibly be achieved if $M$ and $E$ were in the group of three but, as El-Guest explored, you need to add three more students to cover everyone else.

I'd assume that you'd want

to have the students attend which have the maximum number of friendships...

So:

M & E have 6 & 5 friendships respectively, then P,Q,R,D,F,J don't have to go thanks to M; and A,H,K,N,R don't have to go thanks to E. This leaves us with B,C,G,I,L,O who we need to deal with. O is only connected to P,Q,R, so they have to attend; C is connected with G,I,L; and then B is the last one left who has to show up.

The minimum number of students is therefore

5, and they are Megan, Ethan, Billy, Chris, and Orville.