A PROOF OF TUTTE'S REALIZABILITY CONDITION,
Abstract
The paper gives a simple proof of the Tutte's realizability condition for a cut-set (circuit) matrix of a non-oriented graph. First, a minimum non-realizable matrix is defined as a matrix (N U) which satisfies (1) (N U) is not a cut-set (circuit) matrix, (2) (N U) does not satisfy the conditions in the Tutte's theorem, and (3) deleting any column other than that belongs to a unit matrix or any row of any normal form of (N U), the resultant matrix is realizable as a cut-set (circuit) matrix. A proof of the Tutte's theorem in this paper is accomplished by showing that minimum non-realizable matrices do not exist. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1969
- Accession Number
- AD0688834
Entities
People
- Wataru Mayeda
Organizations
- University of Illinois Urbana–Champaign