>What if one of them is a Republican and one is a Democrat? We already see this in some systems today.

It's probably the same graph with two edges added or removed anyway.