Graph Symmetry and Schur's Lemma in Group Representation One famous theorem extended from Schur's Lemma is: 

Let $\vartheta$: $s \mapsto D(s)$ be an irreducible representation of the group $G$ in the representation space $V$, and let $Q$ be a linear operator $V\rightarrow V$ having the symmetry of $\vartheta$; i.e., $QD(s)=D(s)Q$ for all $s\in G$. Then $Q = \lambda I$, where $I$ is the identity matrix.  

Now consider the graph symmetry (automorphism): 

An automorphism of the graph $\mathcal{G}=(V,E)$ is a permutation $\psi$ of its vertex set such that $$\psi(i)\psi(j)\in E \Longleftrightarrow ij\in E$$ 

Associate this permutation $\psi$, we can define the permutation matrix $\Psi$ such that $$[\Psi]_{ij}=\begin{cases}
1 & \text{if }\psi(i)=j\\
0 & \mbox{otherwise }
\end{cases}$$ 
Then $\psi$ is an automorphism of $\mathcal{G}$ if and only if $$\Psi A(\mathcal{G})= A(\mathcal{G})\Psi,$$ wher $A(\mathcal{G})$ is the adjacency matrix of the graph $\mathcal{G}$.

My question:  
Consider the complete graph of three vertices, $K_3$ (triangle). Its adjacency matrix is $$A(K_3) = \begin{bmatrix}0 & 1 & 1\\1 & 0 & 1\\1 & 1 & 0\end{bmatrix}.$$  Consider all permutations of three nodes, then we have six cases: $$(1,2,3),(1,3,2),(3,2,1),(2,1,3),(3,1,2),(2,3,1).$$ Let their corresponding representation matrices are: $$D(s_1), D(s_2), D(s_3), D(s_4), D(s_5), D(s_6).$$ For example:  $$D(s_2)=\begin{bmatrix}1 & 0 & 0\\0 & 0 & 1\\0 & 1 & 0\end{bmatrix}.$$   It is easy to check the following fact by Matlab:  $$D(s_i)A(K_3) = A(K_3)D(s_i), \ \ \forall i.$$  

So it looks like it meets the Schur's Lemma since this representation is irreducible in $V = \mathbb{R}^3$. However, $A(K_3)\neq \lambda I$.  Why? 

 A: In your example, the vector space $V$ is the vector space spanned by three vectors, $v_1, v_2, v_3$ corresponding to the vertices of the graph $K_3$. The adjacency operator $A: V \to V$ acts by
$$ Av_1 = v_2 + v_3, Av_2 = v_1 + v_3, Av_3 = v_1 + v_2$$
On the other hand, we have the symmetric group $S_3$ acting by permutations of these basis vectors:
$$ \sigma \cdot v_i = v_{\sigma(i)}$$
As you have noticed, these always commute (and in fact, it is a general fact that the adjacency operator $A$ of a graph will always commute with graph automorphisms). However, the representation of $S_3$ on $V$ is not irreducible, since for example the vector $w_1 = v_1 + v_2 + v_3$ is fixed under every permutation $\sigma$.
If we take the complementary subspace $U \subseteq V$ to $w_1$, which is
$$ U = \{av_1 + bv_2 + cv_3 \mid a + b + c = 0\}$$
then we do in fact get an irreducible representation. $U$ is spanned by $v_1 - v_2$ and $v_2 - v_3$, and we can check what $A|_U$ does on this basis:
$$ A(v_1 - v_2) = (v_2 + v_3) - (v_1 + v_3) = -(v_1 - v_2)$$
$$ A(v_2 - v_3) = (v_1 + v_3) - (v_1 + v_2) = -(v_2 - v_3)$$
and so $A|_U$ is $- \mathrm{id}_U$.
