I have two proofs by induction. The inductive step of each relies on the other. Is it flawed to have a circular dependence like this?
Both proofs are regarding the existence of paths in a graph. In the first proof ($P$) we show that if a path (that meets a set of criteria) exists in graph $A$ then a corresponding path will exist in graph $B$, where paths correspond to each other if they share the same source and sink node. The second proof ($Q$) shows that if there are two paths (that meet a certain criteria) that share the same source node in $A$, then there will be two paths in $B$ that have the same sinks as the paths in $A$ that also share some source node. The proofs are by induction as some edges in the graph may be inferred due to the existence of a path.
For $P$ to work for a certain criteria of paths, I need $Q$ to be true. For $Q$ to work for a certain criteria of paths (different from the first), I need $P$ to be true.
Edit inspired by the comment from @Gae.S.: If it's helpful, for $P(n+1)$ to be true I need $Q(n)$ to be true, and for $Q(n)$ to be true I need $P(n-1)$ to be true.