**Proof. **
Let *H* be an
*r*×*n* cycle-free parity-check matrix for
,
and let *T* = *T*(*H*) be the corresponding cycle-free Tanner graph
that represents
. The following procedure converts *T* into
a graph , such that
is the cut-set code of .
We will describe this procedure assuming that *T* is a tree,
in which case is connected. In case *T* is a forest consisting
of trees, the same procedure should be carried out
independently for each tree in *T*, and will have
connected components.

Let
= {*y*_{1}, *y*_{2},..., *y*_{r}} be the set of check vertices in *T*,
and let
*X*_{i} denote the neighborhood of
*y*_{i}
for
*i* = 1, 2,..., *r*. Further define
*X*^{*}_{i} = *X*_{1} *X*_{2} ^{ ... } *X*_{i}.
Since *T* is a tree, it is always possible to enumerate
the check vertices in *T* in such a way that *X*_{i} intersects
*X*^{*}_{i-1} in *one and only one* symbol vertex for all *i*.
Given such enumeration
*y*_{1}, *y*_{2},..., *y*_{r},
we construct
iteratively, check-vertex by check-vertex. First, we represent
*y*_{1} and its neighborhood *X*_{1} by a cycle
_{1} consisting
of | *X*_{1}| edges and | *X*_{1}| vertices.
Now suppose that
*X*_{2} *X*_{1} = {*x*_{2}}. Then we create
_{2} from
_{1}
by appending | *X*_{2}| - 1 edges -- one for each symbol vertex in
*X*_{2} except *x*_{2} -- and | *X*_{2}| - 2 vertices, in such
a way that the edges corresponding to the symbol
vertices in *X*_{2} form a cycle in
_{2}.
And so forth: if
*X*_{i} *X*^{*}_{i-1} = {*x*_{i}},
we create
_{i} from
_{i-1}
by appending | *X*_{i}| - 1 edges and | *X*_{i}| - 2 vertices,
in such a way that the edges corresponding to the symbols
in *X*_{i} form a new cycle.
It is easy to see that
= _{r} will contain exactly *n*
edges and
*n* - (*r*-1) vertices. Furthermore, the code
generated by *H* is precisely the cycle code of . Since the
cut-set code of is the dual of its cycle code, our proof
is complete.

width4pt depth2pt height6pt

For example, the cycle-free codes defined by the parity-check matrices in (3.16) and (3.19) are cut-set codes of the graphs depicted in Figure 3.7a and Figure 3.7b, respectively.

For cut-set codes, it is well-known [29,48] that
2*n**md*, where *m* is the number of vertices
in the underlying graph . Indeed, this follows
immediately from the fact that if
the minimum distance
of
is *d*, then every vertex of must
have degree at least *d*, otherwise the cut-set that
isolates this vertex will have less than *d* edges.
It is also well-known
that
, where
()
is the number of connected components in .
Thus we obtain the following cut-set bound
on the minimum distance of cycle-free codes

If it is known that

We have proved that every cycle-free binary linear code is a cut-set code. We now attempt to make this correspondence more precise by examining exactly which cut-set codes correspond to cycle-free binary linear codes. An answer to this question follows from a closer look at the construction in Theorem 3.11 and relies on star graphs, which are graphs where the removal of a vertex, which is connected to all the other vertices, results in a forest.

**Proof. **
Consider a cycle-free Tanner graph *T* for a given
cut-set code, the corresponding
graph from the construction in Theorem 3.11,
and its dual graph
^{D}.
Absent the vertex corresponding to the outer region of ,
each path in
^{D} corresponds to a path through the Tanner graph *T*:
vertices in
^{D} correspond to check nodes of *T*, and
edges in
^{D} correspond to symbol nodes of *T*. Since
a path in *T* cannot contain a cycle, the same is true for
^{D} absent the outer vertex. Thus,
^{D} is a star
corresponding to *T*.

The other direction of the correspondence is similarly straightforward.
Given a cut-set code of a graph whose dual is a star, we may simply
reverse the algorithm in Theorem 3.11 to arrive at a
Tanner graph. This Tanner graph must be cycle free, or else
^{D} has a cycle among vertices other than the outer vertex.

width4pt depth2pt height6pt

http://people.bu.edu/trachten