DMTCS'96 is the first of a planned series of conferences organized by the Centre for Discrete Mathematics and Theoretical Computer Science, and is the first joint venture of the Computer Science and Mathematics departments of the University of Auckland and Waikato, New Zealand. These proceedings contain original papers which had been solicited in all areas of discrete mathematics and theoretical computer science, in particular in the areas of combinatorics, complexity, computability, constructivity, and logic.