T-irreducible extension is one of kinds of optimal extensions of graphs. Constructions of optimal extensions are used in diagnosis of discrete systems and in cryptography. A graph H with n+1 vertices is called an extension of a graph G with n vertices if G can be embedded in every maximal subgraph of H. Any graph Ghas the trivial extension that is the join ng+of G with some outer vertex v. T-irreducible extensions are obtained from the trivial extension by removal of maximal number of edges in such a way that the extension property is preserved.
