# Counting Components via Spectra of Adjacency Matrices

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:

1. Remove the first $\color{red}{\text{edge}}$ (you choose any)
2. and the two resulting $\color{red}{\text{vertices of degree$2$}}$
3. 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

1. setting the offdiagonal entry that represents the $\color{red}{\text{red edge}}$ to $0$,
2. removing the dimensions that represent the $\color{red}{\text{red vertices}}$
3. 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?

#### Solutions Collecting From Web of "Counting Components via Spectra of Adjacency Matrices"

3. It is well known that the number of connected components of a $r$-regular graph is in fact the multiplicity of the eigenvalue $r$.
4. If the graph is in fact bipartite, then it is automatically $2$-connected.
5. It is always possible to reduce a cubic graph of order $n+2$ to a cubic graph of order $n$ by using a so called $H$ reduction with is essentialy what you’re doing here but handles the thing with triangles. See this paper for example.