Setup: I have an undirected (multi)graph $G$ with $n+1$ vertices. Each vertex has degree $\leq 2$, and vertex number $0$ has degree exactly one.
What I'm looking for: I know that any graph with maximum degree $\leq 2$ can be split up into just paths and cycles. Since vertex zero has degree exactly $1$, it must be part of a path. What I'd really like to know is the maximum length (diameter, I guess) of this path.
My thoughts: Since vertex $0$ is part of a path, the part of the graph that it's in is not a multigraph. That means that multiplying the adjacency matrix $A$ by itself ($A^k$) will eventually yield a matrix with all zeros, except for a $1$ in the $0,j$ entry, where $j$ is the end of the path. So one way to get the path length would be to keep squaring $A$ until it looks like this, and then note the parity of $k$.
My question: Is there any way to determine the parity just by looking at the adjacency matrix? I know that maximum path length is in the general case very hard (NP-hard, I think), but given the number of constraints I have on my graph, and that I don't even need path length, just parity, I figured there might be some easier way of doing it.
In general, (i.e., general graphs $G$ on $n$ vertices), if you take a high enough power $k$ of adjacency matrix $A$ of a graph $G$ (where the $ij$-th entry of $A$ is 1 iff $i$ and $j$ are adjacent in $G$), then $A^k$ will be a block matrix: You can partition $V(G)$ into sets $V_1,\ldots, V_m$ for some $m$ where
(i) the $ij$-th entry of $A$ is positive iff $i$ and $j$ are both in the same $V_l$, and
(ii) the $V_l$'s are the connected components of $G$; i.e., $i$ and $j$ are in the same connected compoent of $G$ iff $i$ and $j$ are in the same $V_l$.
In fact, taking $k = 2^{\lceil\log n\rceil}$ will do where $n$ is the number of vertices of $G$.
Meanwhile is there a reason why you just cannot follow the path starting from vertex 0. If the graph has maximum degree 2, then storing $G$ as an adjacency matrix is extremely inefficient use of space.