On Adjacency Matrix of a Graph with a Cut Vertex and a Bridge

Question

Let $G$ be a graph. If $v_i$ (resp. $v_iv_j$) is a cut vertex (resp. a bridge) of $G$, what can you say about its adjacency matrix $A(G)$?

Answer 1

When you have a graph with two components, you can treat each component as its own graph in terms of the adjacency matrix. One of the most basic results is that the spectrum of $G$ is the spectrum of each of its components. So if I have two disconnected instances $C_{3}$ for my graph, then my eigenvalues are $2$ with multiplicity two, and $-1$ with multiplicity four.

Edit to expand some on the spectrum:

Spectra vary upon graphs, so that factors into it. Immediately in the characteristic polynomial, we note that the edge count and triangle count are encoded. We can get this by looking at the cofactors. So the coefficient of $\lambda^{n-2}$ is increased by $1$, as $c_{2} = -|E|$ of the graph. Similarly, we note that $c_{3}$, the coefficient of $\lambda^{n-3} = -2C_{3}$, twice the number of triangles in the graph. That won't change since the edge removed is a cut edge.

We also look at our trace-eigenvalue identity. So $\sum_{i=1}^{n} \lambda_{i} = tr(A) = 0$ on a simple graph. Squaring the adjacency matrix gives the diagonal entries as counting the edges. So $\sum_{i=1}^{n} \lambda_{i}^{2} = tr(A^{2}) = 2E$, and $\sum_{i=1}^{n} \lambda_{i}^{3} = tr(A^{3}) = 6C_{3}$. (I am happy to provide more proof if desired). So we see removing a cut edge will change $tr(A^{2})$ but not $tr(A^{3})$.

Another nice example to look at is the star graph on $n$ vertices. Its spectrum is $\pm \sqrt{n-1}$, each with multiplicity one; and $0$ with multiplicity $n-2$. Interestingly enough, $S_{n} - e$, for some $e \in E(S_{n})$ gives us the characteristic polynomial for $S_{n-1}$.

Removing an edge won't change whether or not the graph is bipartite, so the spectrum will still be symmetric to the origin. This means that $\lambda_{i} = -\lambda_{n-i}$. If $G$ is connected, we only have to check that $\lambda_{1} = -\lambda_{n}$ to determine if $G$ is bipartite. However, if $G$ is not connected (by removal of a cut edge), we have to check the entire spectrum. So this quickly goes from a $\Theta(1)$ operation (given the spectrum) to a $\Theta(n)$ operation.

There are textbooks on spectral graph theory; and given the lack of focus of the question, you can see that it's hard to really focus down. These properties constitute probably 10 pages in the textbook I own on the subject.