On the invertibility of the adjacency matrix of a graph

As far as I know, there is no "simple" necessary and sufficient condition of $G$ for an invertible adjacency matrix. A few comments:

• A necessary condition that generalizes your "each vertex needs at least one connection" condition is that if $S$ is any subset of vertices of the graph, there are at least $|S|$ vertices in the graph having at least one neighbor in $S$ (including possibly vertices in $S$ itself). This is because the rows of the adjacency matrix corresponding to $S$ need to have at least $|S|$ different columns with a non-zero entry to be independent.

This necessary condition is not sufficient. For example, a $4$ cycle has the expansion property, but a singular adjacency matrix.

• A special case of the above: If $G$ is bipartite with non-singular adjacency matrix, both halves of the bipartition have equal size.

• The property is not in general what is termed "monotone" -- adding edges to an invertible graph can both turn a non-singular matrix into a singular one and vice versa (e.g. closing a path on $3$ vertices to a triangle vs. closing a path on $4$ vertices to a $4$ cycle).

• It's been conjectured that the vast majority of singular adjacency matrices are caused by pairs of vertices having identical neighborhoods (these correspond to pairs of equal rows in the adjacency matrix). In other words, if we look at all graphs on $n$ vertices, then it is believed that $$\frac{|\{G \textrm{ with at least one pair of identical neighborhoods }\}|}{|\{G \textrm{ with singular adjacency matrix }\}|} \rightarrow 1$$ as $n$ goes to infinity. however, this is still an open problem. The numerator is an $O\left(n^2 2^{-n}\right)$ fraction of all $n$-vertex graphs, and the best known result is that the denominator is a $\exp(-n^c)$ fraction of graphs for some small positive $c$ (Vershynin was the first to prove a bound of this form. The current best value of $c$ is due to Ferber and Jain).

I think a general set of conditions will be hard to come by. To substantiate this claim I make the following negative observation.

The adjacency matrix of any bipartite graph with an odd number of vertices is not invertible.

This follows since the eigenvalues of a bipartite graph are symmetric about $0$, and since there are an odd number of eigenvalues (if the graph has an odd number of vertices) then at least one of these is $0$.

You may find the following reference useful:

• Sciriha, Irene. "A characterization of singular graphs." Electronic Journal of Linear Algebra 16.1 (2007): 38.

It describes necessary and sufficient conditions for the adjacency matrix of a simple graph to be singular (non-invertible). Be forewarned: these do not appear to be particularly "nice" conditions.