Take the 2-minute tour ×

Let $X$ be a connected graph with maximum eigenvalue $k$. Assume that $-k$ is also an eigenvalue. I wish to prove that $X$ is bipartite.

Now if $\vec{x}=(x_1,\cdots ,x_n)$ is the eigenvector for $-k$ then I can show that for the vector $\vec{y}$ whose entries are $(|x_1|,\cdots ,|x_n|)$ we have $y'Ay=ky'y$. From here can I conclude that $\vec{y}$ is an eigenvector with eigenvalue $k$?

How to proceed to prove this result?


share|improve this question
You must assume $G$ is connected. In (2.), $m=n$. I don't understand your point (3.). –  Colin McQuillan Oct 27 '12 at 7:28

3 Answers 3

up vote 4 down vote accepted

$A$ is symmetric, nonnegative, and irreducible. By a theorem of Perron and Frobenius, $k$ is a simple eigenvalue with a positive eigenvector $u$. Now with componentwise absolute value, $k|x|=|-kx|=|Ax|\le A|x|$. Multiplication with $u^T$ shows that we must have equality. Hence $|x|$ is an eigenvector, hence a multiple of $u$. Therefore $x$ has no zero component.

Partition the nodes into $P$ and $N$, where $x_i>0$ if $i\in P$ and $x_i<0$ if $i\in N$. Then $v=x_P>0$ and $w=-x_N>0$. Partition $A$ conformally as $A=\pmatrix{B & C\\C^T & D}$, and note that $B,C,D$ are nonnegative. Then the equation $|Ax|= A|x|$ implies $|Bv-Cw|=Bv+Cw$ and $|C^Tv-Dw|=C^Tv+Dw$. This yields $(Bv)_i(Cw)_i=0$ for $i\in P$ and $(C^Tv)_k(Dw)_k=0$ for $k\in N$. Since $v,w>0$, $C_{ik}=1$ implies that $B_{ij}=0$ for $j\in P$ and $D_{kj}=0$ for $j\in N$.

This means that for every edge $ik$ with $i\in P$ and $k\in N$, the neighbors of $i$ must lie in $N$ and the neighbors of $k$ must lie in $P$. Growing the graph starting with some such edge implies that its connected component is bipartite. On the other hand, if there is no such edge then $P$ and $N$ are unions of connected components. Since the graph was assumed connected, it follows that it is bipartite.

share|improve this answer
I do not follow why $ku'|x|=u'A|x|$ implies that $|x|$ is an eigenvector. Can you explain please? –  Shahab Nov 13 '12 at 6:28
@Shahab: It implies that $k|x|=A|x|$. For if this fails then there is strict inequality in at least one component, and multiplication by $u^T>0$ gives a strict inequality, contradiction. –  Arnold Neumaier Nov 13 '12 at 10:14

(This answer is for an older version of the question where the graph is assumed to be $k$-regular.)

Let $(v_1,\dots,v_n)$ be an eigenvector of the adjacency matrix, with eigenvalue $-k$. This means that $$-kv_i = \sum_{j\sim i} v_j$$ for all $i\in V$, where $j\sim i$ means that $i$ and $j$ are adjacent. Let $M=\max_i|v_i|$ and $P=\{i\mid v_i=M\}$ and $N=\{i\mid v_i=-M\}$.

For every $i\in P$ we have $-kM=-kv_i=\sum_{j\sim i} v_j$. But, because $v_j\geq -M$ for all $j$, the only way to achieve $\sum_{j\sim i} v_j = -kM$ is if $v_j=-M$ for all $j\sim i$, or in other words $j\in N$. Similarly for every $i\in N$ we have $j\in P$ for all $j\sim i$. The graph induced by $P\cup N$ is therefore a bipartite connected component.

share|improve this answer
Could you please complete the proof or give some more hints? –  user844541 Dec 3 '12 at 22:54
@user844541: my answer is for an older version of the question where the graph is assumed to be $k$-regular. For this special case, we can argue that set $\{i\mid |v_i|=\max_j |v_j|\}$ is connected because $-kv_i= \sum_{i\sim j} v_j$, so we can avoid Perron--Frobenius as used in the other answers. –  Colin McQuillan Dec 4 '12 at 0:30
I am working with a d-regular graph. I was able to complete the proof based on the assumption that |v1|= |v2|=...=|vn|, but I wasn't able to prove that.. –  user844541 Dec 4 '12 at 8:06
@user844541: ok, I've filled out the answer a bit. –  Colin McQuillan Dec 4 '12 at 11:57
Thanks a lot!!! –  user844541 Dec 4 '12 at 18:32

As Colin noted in a comment, you need to assume that $G$ is connected.

For a $k$-regular graph, $\mathbf A/k$ is the transition matrix of a random walk that uniformly selects one of the $k$ neighbours in each step. If $\mathbf A$ has eigenvalue $-k$, then $\mathbf A/k$ has eigenvalue $-1$. Thus the random walk does not necessarily converge to a stationary distribution. Since $G$ is connected, the Markov chain is irreducible, so there must be a periodic state. In an undirected graph, the only possible period is $2$. Thus the graph decomposes into the sets of vertices that are even and odd with respect to that period, and is thus bipartite.

share|improve this answer

Your Answer


