Not entirely sure if I agree with the explanation of your SEO guy as rel=prev and rel=next are used for paginated archives.
Of course categories can be one, but also your blog if it’d contain multiple pages.
Anyways, here’s what I’m currently using:
remove_action( 'wp_head', 'adjacent_posts_rel_link_wp_head' );
add_action( 'wp_head', 'cor_rel_next_prev_pagination' );
/**
* Pagination with rel="next" and rel="prev".
*
* @link wp-includes|default-filters.php
* @link http://core.trac.wordpress.org/ticket/18672 Implement rel="prev" and rel="next" for archives
* @link http://googlewebmastercentral.blogspot.com/2011/09/pagination-with-relnext-and-relprev.html Pagination with rel="next" and rel="prev"
*/
function cor_rel_next_prev_pagination() {
global $paged;
if ( get_previous_posts_link() ) {
?>
<link rel="prev" href="https://wordpress.stackexchange.com/questions/47638/<?php echo get_pagenum_link( $paged - 1 ); ?>">
<?php
}
if ( get_next_posts_link() ) {
?>
<link rel="next" href="<?php echo get_pagenum_link( $paged + 1 ); ?>">
<?php
}
}
Edit: also I believe start_post_rel_link
is no longer being used.