50 Depth of a circuit

Definition (Depth)

• The depth of a circuit $C$ is the length of the longest path through its underlying graph, counting number of edges
• The depth of a node is the length of the longest path from a source to that node

NB: induction on circuit structure $\approx$ induction on depth

This circuit has depth 3, witnessed by two longest paths:

• $x_1,1,3,s$ is a path of length 3.
• $x_2,2,4,s$ is a path of length 3. Thus $x_1,x_2$ have depth $0;1,2$ have depth $1;3,4$ have depth $2$; and $s$ has depth $3$.