HW1

1. Let $A$ be the adjacency matrix of a graph $G=(V,E)$.

• (a) Find a combinatorial interpretation for each entry of $A^2$ and $A^3$.
• (b) Show that $\mathrm{tr}\left(A^2\right)=2|E|$.
• (c) For $m\ge 2$ an integer, what does $\mathrm{tr}\left(A^m\right)$ count? Prove your claim.

简单计算

2. The girth of a graph $G$ is the length of the smallest polygon in the graph. Let $G$ be a graph of girth 5 for which all vertices have degree at least $d$. Show that $G$ has at least $d^2+1$ vertices. Can equality hold?

从一个点出发，走两层都没有交，这已经 $d^2+1$ 个点了

3. Let $Q=\{1,\dots ,q\}$ be the graph with vertex set $Q^n$, two vertices adjacent if they differ in exactly one coordinate. Show that $Q$ is Hamiltonian.

把每层的 Hamilton circuit 用对应的边粘起来

4. Find the six nonisomorphic trees on 6 vertices, and for each compute the number of distinct spanning trees in $K_6$ isomorphic to it.

标号得到的就是不同的 tree，考虑不同编号方式

5.

• (a) Suppose a tree $G$ has exactly one vertex of degree $i$ for $2\le i\le m$ and all other vertices have degree 1 . How many vertices does $G$ have?
• (b) Suppose a graph $G$ has exactly one vertex of degree $i$ for $2\le i\le m$ and $k$ other vertices have degree 1 . Prove that $k\ge \lfloor \frac{m+3}{2}\rfloor$ give a construction for such a graph.

a) 简单计算

b) 把graph $G$ 拆成两个子图，分别计算两个子图的 $\sum \mathrm{deg}(v)$，相减把 k 取出来，用度数多的放成完全图来放缩。