Signed Graph - Fundamental Theorem

Fundamental Theorem

A signed graph is balanced if and only if its vertex set can be divided into two sets (either of which may be empty), X and Y, so that each edge between the sets is negative and each edge within a set is positive. This is the first theorem of signed graphs (Harary, 1953). It generalizes the theorem that an ordinary (unsigned) graph is bipartite if and only if every cycle has even length.

A simple proof uses the method of switching. To prove Harary's theorem, one shows by induction that Σ can be switched to be all positive if and only if it is balanced.

A weaker theorem, but with a simpler proof, is that if every 3-cycle in a signed complete graph is balanced, then either all nodes are connected by positive edges or the nodes can be divided into two groups A and B such that every pair of nodes in A are connected by a positive edge, every pair of nodes in B are connected by a positive edge, and all edges going between A and B are negative edges. For the proof, pick an arbitrary node n and place it and all those nodes that are linked to n by a positive edge in one group, called A, and all those linked to n by a negative edge in the other, called B. Since this is a complete graph, every two nodes in A must be friends and every two nodes in B must be friends, otherwise there would be a 3-cycle which was unbalanced. (Since this is a complete graph, any one negative edge would cause an unbalanced three cycle.) Likewise, all negative edges must go between the two groups.