Not what you are looking for. But just for the purpose sharing knowledge, you can do that with $O(|E|)$ messages if you assume that each vertex to act as a processor. Note each vertex has a comparable value. Therefore, there exists some vertices such that they are larger than all their neighbors. These vertices do the following:
- Let $u$ be the maximum smaller neighbor of $v$,
- send a message to $u$ and include edge $(v,u)$ in the output.
- For every neighbor $w$ of $u$ and $v$ (and smaller than both), do not include $(v,w)$ in the output.
- Repeat the steps until all edge $(v,v')$ for a smaller neighbor $v'$ of vertex $v$ is either included or not included in the output.
Now if a node $v$ received a message from every larger neighbor (i.e. all the edges $(v',v)$ are either included or not included, then node $v$ acts as if it was the largest in its neighborhood. That is, it performs the previously mentioned 4 steps.
This algorithm terminates in $O(|E|)$ messages in a distributed environment. I know this is not what you are asking for.