Exercise 2
先证充分性。如果 $ G $ 是一个二分图，设两部分的点集分别为 $ L,R $，所有边均满足两端点分别在 $ L,R $ 中。反证法，加入存在奇环，设环中第一和最后一个点分别为 $ v_{1},v_{k} $，那么 $ k $ 为奇数。不妨设 $ v_{1}\in L $，由于一条边必然在 $ L,R $ 两部分之间 ，所以环中的点在 $ L,R $ 交替出现，即 $ v_{2}\in R,v_{3}\in L,\dots $，由于 $ k $ 是奇数，因此 $ v_{k}\in L $。这说明 $ v_{1},v_{k} $ 两个 $ L $ 中的点存在连边，与二分图矛盾。因此二分图中没有奇环。
再证必要性。如果 $ G $ 没有奇环，我们可以将 $ G $ 分成若干个连通块，每个连通块中任取一个点 $ u_{i} $，我们按照一下顺序将所有点分成 $ L,R $ 两组：首先令 $ u_{i}\in L $，将所有与 $ u_{i} $ 最短距离为偶数的点加入 $ L $，其余的点，也就是到 $ u_{i} $ 最短距离为奇数的点加入 $ R $。
下面我们证明这是一个二分图，也就是证明所有 $ L $ 中的点两两不连边，所有 $ R $ 中的点也两两不练边。设 $ v_{1},v_{2}\in L $，如果这两个点不在一个连通块内，那么显然 $ v_{1},v_{2} $ 之间没有边；如果两个点在一个连通块内，设这个连通块中之前选取的代表点 $ u $，我们知道 $ d(u,v_{1}),d(u,v_{2}) $ 均为偶数，如果边 $ \{ v_{1},v_{2} \} $ 存在，那么我们就找到了一个长度为奇数的环 $ u\dots v_{1}v_{2}\dots u $，矛盾，因此此时 $ v_{1},v_{2} $ 之间也没有边。对于 $ R $ 中的两个点，同理，如果两个点在一个连通块，那么假设边存在，选取对应连通块的代表元素 $ u $，也找到了奇数环 $ u\dots v_{1}v_{2}\dots u $，矛盾。所以 $ L $ 和 $ R $ 中一个集合内的点两两都没有连边，这是一个二分图。证毕！
Exercise 3
(1)
由于 $ G $ 是 $ d $-正则图，所以最大的特征值 $ \lambda_{1}=d $。如果 $ G $ 不连通，那么至少可以被划分为两个连通块 $ G_{1},G_{2} $。我们为每个连通块都定义一个特征向量，对于 $ G_{1} $，我们构造向量 $ v_{1} $，其中对应在 $ G_{1} $ 中顶点的元素为 $ 1 $，其余为 $ 0 $。
此时当邻接矩阵乘以 $ v_{1} $，由于 $ G_{1} $ 和其他连通块之间都没有边，因此对于 $ G_{1} $ 中的每个点，结果都是 $ d $，其余的点都是 $ 0 $，所以就有 $$ Av_{1} = dv_{1} $$ 对于 $ G_{2} $，同理也能构造出这样 $ v_{2} $。并且 $ v_{1},v_{2} $ 显然是线性无关的，这样我们就找到了两个特征值 $ d $ 对应的特征向量，说明 $ d $ 的几何重数至少是 $ 2 $，从而代数重数也至少是 $ 2 $，所以必然有 $$ \lambda_{1}=\lambda_{2}=d $$ (2)
由于 $ d $-正则图的性质，我们知道 $ \left| \lambda \right|\leq d $，因此我们只需要证明 $ -d $ 是一个特征值即可说明最小的特征值 $ \lambda_{n}=-d $。
对于二分图 $ G $，我们可以将点集 $ V $ 分成不相交的 $ U,W $ 两个集合，使得每条边的两个端点分别属于 $ U,W $。我们构造向量 $ v $ 满足所有 $ U $ 中的点对应的元素为 $ 1 $，所有 $ W $ 中的点对应的元素为 $ -1 $。根据二分图和正则图的性质，我们就知道 $$ Av = -dv $$ 因为 $ U $ 中的点对应行中只有 $ W $ 中的点值为 $ 1 $，共有 $ d $ 个，乘以 $ v $ 以后就会得到 $ -d $。$ W $ 中的点同理。
由于 $ v $ 是一个非零向量，那么根据特征值的定义，我们就得到了 $ -d $ 是一个特征值，从而 $$ \lambda_{n}=-d $$
Exercise 6
由于每个顶点 $ v $ 和所有通过路径可以和 $ v $ 相连的顶点构成的集合是一个联通子图，因此 $ v $ 至少属于一个连通分量。
假设 $ u $ 同时属于两个不同的连通分量 $ C_{1},C_{2} $，那么对于 $ v_{1}\in C_{1},v_{2}\in C_{2} $，我们知道存在从 $ u $ 到 $ v_{1} $ 和 $ u $ 到 $ v_{2} $ 的路径，从而说明存在 $ v_{1} $ 到 $ v_{2} $ 的路径，从而与定义矛盾。
因此每个顶点唯一地属于一个连通分量。
接着证明如果 $ G $ 不连通，当且仅当 $ G $ 包含至少两个连通分量。首先如果 $ G $ 不连通，那么存在 $ u,v $ 满足 $ u,v $ 之间不存在任何路径相连，如果 $ u,v $ 属于一个连通分量，那么则与定义矛盾，所以 $ u,v $ 一定分开属于两个连通分量，因此 $ G $ 至少包含两个连通分量。如果 $ G $ 至少包含两个连通分量，那么取两个属于不同连通分量的点 $ u,v $，我们可以知道 $ u,v $ 之间不存在路径，因此 $ G $ 不连通。
Exercise 7
($ \Rightarrow $) 假设 $ G $ 有一个连通分量 $ C $ 是二部图。我们可以将 $ C $ 的点集 $ V(C) $ 分成不相交的 $ U,W $ 两个集合，使得 $ C $ 中每条边的两个端点分别属于 $ U $ 和 $ W $。我们构造向量 $ x $ 满足所有 $ U $ 中的点对应的元素为 $ 1 $，所有 $ W $ 中的点对应的元素为 $ -1 $，而所有不在 $ C $ 中的点对应的元素为 $ 0 $。根据二部图和 $ d $-正则图的性质，对于任何 $ U $ 中的点，其 $ d $ 个邻居都在 $ W $ 中，因此 $ A $ 的对应行与 $ x $ 相乘得到 $ d \times (-1) = -d $。同理，对于任何 $ W $ 中的点，其 $ d $ 个邻居都在 $ U $ 中，相乘得到 $ d \times (1) = d = -d \times (-1) $。对于不在 $ C $ 中的点，其邻居也不在 $ C $ 中，相乘结果为 $ 0 $。因此，我们就知道 $ Ax = -dx $。由于 $ x $ 是一个非零向量，那么根据特征值的定义，$ -d $ 是一个特征值。又因为对于 $ d $-正则图的所有特征值 $ \lambda $ 均满足 $ |\lambda| \leq d $，我们从而得到最小特征值 $ \lambda_{n}=-d $。
($ \Leftarrow $) 假设 $ \lambda_{n}=-d $。令 $ x $ 为其对应的非零特征向量，满足 $ Ax = -dx $。因为 $ x $ 非零，所以必定存在一个连通分量 $ C $ 使得 $ x $ 在 $ C $ 上的分量不全为零。在 $ C $ 中取一个顶点 $ v $ 使得其分量的绝对值 $ |x_v| $ 最大，令 $ M = |x_v| > 0 $。不失一般性，设 $ x_v=M $。根据特征值方程有 $ \sum_{u \sim v} x_u = -d x_v = -dM $。由三角不等式可得 $ dM = |-dM| = |\sum_{u \sim v} x_u| \le \sum_{u \sim v} |x_u| $。又因为 $ M $ 是最大绝对值，我们有 $ \sum_{u \sim v} |x_u| \le \sum_{u \sim v} M = dM $。因此上述不等式必须取等，这意味着 $ v $ 的所有邻居 $ u $ 必须满足 $ |x_u|=M $ 且符号与 $ x_v $ 相反，即 $ x_u = -M $。此论证可以沿 $ C $ 中的路径传递，说明 $ C $ 中所有顶点的分量绝对值均为 $ M $。于是我们可以将 $ C $ 的点集划分为 $ U=\{u \in V(C) \mid x_u=M\} $ 和 $ W=\{w \in V(C) \mid x_w=-M\} $。根据构造， $ C $ 中的任意一条边都连接着 $ U $ 和 $ W $ 中的顶点，因此连通分量 $ C $ 是一个二部图。