1. Let $G(V,E)$ be a graph. We construct the matrix $C$ as
follows: $C[i,j]=1$ iff $i \neq j$ and $(i,j)\in E$. Thus $C$
is the `actual' adjacency matrix of the graph $G$.
Under what condition will $C^n [i,j] $ be non-zero?
2. We have defined the sign of a permutation on the numbers $\{
1,2, \ldots ,n \}$ which depended on comparing $i$ and $j$ as
numbers. Let $X$ be a set of size $n$ and $\phi $ be a bijection
on $X$. Can you associate a sign with $\phi $? Do different
definitions give a different sign?
3. Let $G(V,E)$ be a connected graph such that for any $i,j$
there is a unique path from $i$ to $j$. Show that $G$ must be a
tree. Also, prove the converse.
4. Let $d(v)$ be the degree of a vertex $v$. Show that
$\sum_{v\in V} d(v)$ is an even number.
5. Recall the edge-adjacency matrix $B$. Suppose we are given a
resistive network, i.e., a graph with vertices and edges either
as resistors or as voltage/current sources. Use $B$ to interpret
Kirchoff's current and voltage laws. Any idea how does one
systematically solve this network?
6. Let $B'$ be the reduced edge adjacency matrix. Show that
$det(B B^T)$ (where $B^T $ is the transpose of $B$) is the number
of spanning trees in $G$.