Abstract: For a hypergraph $H=(V,E)$, a hypergraph $H'=(V,E')$ is called a $k$-certificate of $H$ if it preserves all the cut values up to $k$. That is, $|\delta_{H'}(S)| \geq \min(|\delta_H(S)|,k)$ for all $S\subset V$. Nagamochi and Ibaraki showed there exists a $k$-certificate with $O(kn)$ edges for graphs, where $n$ is the number of vertices. A similar argument shows this extends to hypergraphs. We show a stronger result of hypergraphs: there is a $k$-certificate with size (sum of degrees) $O(kn)$, and it can be obtained by removing vertices from edges in $H$. We also devise an algorithm that finds a representation of all min-cuts in a hypergraph in the same running time as finding a single min-cut. The algorithm uses Cunningham's decomposition framework, and different generalizations of maximum adjacency ordering. This is joint work with Chandra Chekuri.