Here's my second attempt:

#! perl -slw
use strict;

my $n = <>;
my %pairings;
push( @{ $pairings{ $_->[0] } }, $_->[1] ),
push( @{ $pairings{ $_->[1] } }, $_->[0] ),
    while @{ $_ = [ split ' ', <> ] };

my $total = 0;
my @guests;
while( $total < $n ) {
    my $next = (
        sort{
            @{ $pairings{ $b } } <=> @{ $pairings{ $a } }
        } keys %pairings
    )[ 0 ];
    push @guests, $next;
    $total += @{ $pairings{ $next } };
    delete $pairings{ $_ } for @{ delete $pairings{ $next } };
}
print scalar @guests;
print for @guests;
[download]

It is still incomplete in that it doesn't yet favour employee 1009 in the event of their being an equally valid choice. I'll think about how to do that whilst I try to find an example that breaks it. (Generating random datasets is quite easy; verifying the answers produced not so:( )

Update: Added code to favour 1009:

#! perl -slw
use strict;

my $n = <>;
my %pairings;
push( @{ $pairings{ $_->[0] } }, $_->[1] ),
push( @{ $pairings{ $_->[1] } }, $_->[0] ),
    while @{ $_ = [split ' ', <> ] };

my $total = 0;
my @guests;
while( $total < $n ) {
    my( $best, $next ) = (
        sort{
            @{ $pairings{ $b } } <=> @{ $pairings{ $a } }
        } keys %pairings
    )[ 0, 1 ];

    $best = $next
        if $next == 1009
        and @{ $pairings{ $best } } == @{ $pairings{ $next } };

    push @guests, $best;
    $total += @{ $pairings{ $best } };
    delete $pairings{ $_ } for @{ delete $pairings{ $best } };
}
print scalar @guests;
print for @guests;
[download]