{ cut -f1 input_graph; cut -f2 input_graph; } | sort | uniq
No need to sort twice.
The { cmd1; cmd2; } syntax is equivalent to (cmd1; cmd2) but may avoid a subshell.
In another language (e.g. Perl), you could slurp the first column in a hash and then process the second column sequentially.
With Bash only, you can avoid temporary files by using the syntax cat <(cmd1) <(cmd2)
. Bash takes care of creating temporary file descriptors and setting up pipelines.
In a script (where you may want to avoid requiring bash), if you end up needing temporary files, use mktemp