I trying to implement a test for $k$-connectedness of cubic triangle-free graphs $G$ given their adjacency matrix $A$. My idea is the following:
For $1$-connectedness, we construct a new graph $G'$ by the following process:
- Remove the first $\color{red}{\text{edge}}$ (you choose any)
- and the two resulting $\color{red}{\text{vertices of degree $2$ }}$
- and reconnect the left-over vertices:
$\hskip2in$
[Since triangles are forbidden, the graph will stay simple.]
This can be done for the adjacency matrix as well by
- setting the offdiagonal entry that represents the $\color{red}{\text{red edge}}$ to $0$,
- removing the dimensions that represent the $\color{red}{\text{red vertices}}$
- and setting the offdiagonal entry that represents the $\color{black}{\text{black edges}}$ to $1$.
By that, we get $A'$ of $G'$ and will then calculate the eigenvalues of $A'$. We do this for all edges. If the graph was initially $1$-connected and we, at a certain point, remove the $\color{red}{\text{bridge }}$, we are left with two components and the spectrum of $A'$ will have two eigenvalues of $3$.
If there is no bridge, we continue with removing pairs of edges, calculate the spectra and watch out for multiple eigenvalues to check for $2$-connectedness and so forth.
Is there any reason why this shouldn't work? How would this algorithm compare to the ones given at Wikipedia?
... More generally, it is easy to determine computationally whether a graph is connected (for example, by using a disjoint-set data structure), or to count the number of connected components...
Seem like I invented counting components via spectra of adjacency matrices?