Title :
A new proof of the colored branch Theorem
Author_Institution :
Dept. of Electr. Eng. & Inf. Technol., Dresden Univ. of Technol., Germany
fDate :
4/1/2006 12:00:00 AM
Abstract :
The colored branch theorem is a result from graph theory that has been described first by Minty. It states the existence of certain meshes and cuts in a graph, whose edges are colored red, green and blue, respectively. The theorem, sometimes also referred to as the lemma of the colored arcs, can be utilized to give short and elegant proofs of many other theorems in graph and circuit theory and has therefore turned out to be of vital importance. We present a new set theoretic proof of the colored branch theorem, that reveals its relationship to the orthogonality theorem, another well-known fundamental result about meshes and cuts in a graph.
Keywords :
graph colouring; theorem proving; circuit theory; colored arcs; colored branch theorem; graph theory; meshes; orthogonality theorem; theorem proving; Circuit theory; Circuit topology; Graph theory; Information technology; Mathematical analysis; Colored branch theorem; cuts; graph theory; meshes; orthogonality theorem;
Journal_Title :
Circuits and Systems II: Express Briefs, IEEE Transactions on
DOI :
10.1109/TCSII.2005.862177