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.
Read more about this topic: Signed Graph
Famous quotes containing the words fundamental and/or theorem:
“What is wanted—whether this is admitted or not—is nothing less than a fundamental remolding, indeed weakening and abolition of the individual: one never tires of enumerating and indicting all that is evil and inimical, prodigal, costly, extravagant in the form individual existence has assumed hitherto, one hopes to manage more cheaply, more safely, more equitably, more uniformly if there exist only large bodies and their members.”
—Friedrich Nietzsche (1844–1900)
“To insure the adoration of a theorem for any length of time, faith is not enough, a police force is needed as well.”
—Albert Camus (1913–1960)