# Question regarding a particular type of graph

Let $$G = (V,E)$$ be a directed graph where every vertex is represented by an $$n$$ bit string. The edges are represented by two polynomial-sized circuits $$S$$ and $$P$$. There is an edge from $$u$$ to $$v$$ if and only if $$S(u) = v$$ and $$P(v) = u$$. I am trying to prove:

• $$G$$ just contains paths, cycles, or isolated vertices.
• Let $$A_{G}$$ be the adjacency matrix of $$G$$. Consider $$H = \frac{1}{2} A_{G}$$. Then, $$||H||_{2} = 1$$.
• The out-degree and in-degree of each vertex are at most 1. Does that help? – Yuval Filmus Oct 13 at 9:01
• Why do we need to divide by $1/2$ for the second case? Isn't $||A_{G}||_{2} = 1$ already? – BlackHat18 Oct 13 at 9:28
• I am guessing that this relates to the fact that there could be vertices of degree 2. – Yuval Filmus Oct 13 at 9:39
• As in, a vertex which has out-degree 1 and also a self-loop? – BlackHat18 Oct 13 at 9:48
• No, as in all vertices in a (directed) cycle. – Yuval Filmus Oct 13 at 10:07