I want to show that $1^T(tI-B)^{-1}\mathbb{1}=0$ when $B$ is the adjacency matrix of a regular graph on $2m$ vertices, where $1$ denotes the all ones vector. This is part of a bigger problem and it's the last step I need to finish. I don't know how to start, because inverting the matrix $tI-B$ already seems very complicated. Could someone help me?
Linear Algebra – Prove 1^T(tI-B)^-1?=0 for Adjacency Matrix of Regular Graph
algebraic-graph-theorygraph theorylinear algebramatrices
Related Solutions
Suppose that $G$ is $d$-regular. Then every vertex of $G$ is adjacent to $d$ other vertices, so each row of its adjacency matrix $A$ will have $d$ $1$’s and $n-d$ $0$’s. Let
$$A=\pmatrix{a_{11}&a_{12}&\dots&a_{1n}\\ a_{21}&a_{22}&\dots&a_{2n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{n1}&a_{n2}&\dots&a_{nn}}\;,$$
and $\vec v$ be the $n\times 1$ vector whose entries are all $1$:
$$\vec v=\pmatrix{1\\1\\\vdots\\1}\;.$$
The product $\vec u=A\vec v$ is an $n\times 1$ vector whose $i$-th entry is $$u_i=\sum_{j=1}^na_{ij}\cdot1=a_{i1}+a_{i2}+\ldots+a_{in}\;.$$ Since $d$ of the numbers $a_{i1},\dots,a_{in}$ are $1$ and the rest are $0$, $u_i=d$ for every $i$. Thus, $$\vec u=\pmatrix{d\\d\\\vdots\\d}=d\vec v\;.$$ That is, $A\vec v=d\vec v$, so by definition $\vec v$ is an eigenvector of $A$ for the eigenvalue $d$.
To show the other direction, you can try to reverse this argument; that works. Alternatively, you can assume that $G$ is not $d$-regular and show that $\vec v$ is not an eigenvector for an eigenvalue $d$; that also works and may be even easier.
The dual of a planar graph depends on how it is embedded in the plane: "The same planar graph can have non-isomorphic dual graphs." (See Wikipedia illustration.)
Although this graph is not regular, it can be modified to obtain a cubic (3-regular) graph with more than one planar embedding and associated nonisomorphic dual graphs. Replace the left- and right-hand vertices of degree two in the top diagram with a "diamond" subgraph, connecting to its top and bottom nodes to produce all nodes of degree 3:
Now the outer face of the top graph will have its maximum degree 10, but the corresponding replacement in the alternative embedding yields a maximum degree 7 (shared by the outer face and one inner face). So the dual (multi-)graph depends on the embedding and cannot be inferred only from the adjacency matrix of the original graph.
So I'd say in the general sense you've asked, it cannot be done without pencil-and-paper or some other visualization of the embedding.
Best Answer
Summing up the $i$th row of $B$ means counting the number of neighbors of the node $i$ in the graph. For a $d$-regular graph, this will be $d$ (constant across nodes). That is, $B\mathbf{1}=d\mathbf{1}$. Further, you have that $\left(I-B/t\right)^{-1}= \sum_{i=0}^{\infty} B^{i}/t^{i}$, whenever the spectral radius of $B/t$ is smaller than $1$, i.e., $\rho(B/t)<1$. This is equivalent to $\left|d/t\right|<1$ or $d<|t|$, as the eigenvalue $d$ happens to be also the spectral radius of $B$. Under the assumption $0\neq d<|t|$, you have
$$\left(I-\frac{B}{t}\right)^{-1}\mathbf{1}=\left(\sum_{i=0}^{\infty} \frac{B^{i}}{t^{i}}\right)\mathbf{1}= \left(\sum_{i=0}^{\infty} \frac{d^i}{t^i}\right)\mathbf{1}=\left(\frac{1}{1-\frac{d}{t}}\right)\mathbf{1}.$$ Therefore, if $0\neq d<|t|$, then
$$\mathbf{1}^{\top}\left(tI-B\right)^{-1}\mathbf{1}=\left(1/t\right)\mathbf{1}^{\top}\left(I-\frac{B}{t}\right)^{-1}\mathbf{1}=\frac{N}{t-d}\neq 0,$$ where $N=2m$ is the number of nodes in the graph.