91Ó°ÊÓ

In each of 8-21, either draw a graph with the given specifications or explain why no such graph exists. Graph, connected, six vertices, five edges, has a nontrivial circuit

Prove that if \(G\) is a graph with spanning tree \(T\) and \(e\) is an edge of \(G\) that is not in \(T\), then the graph obtained by adding \(e\) to \(T\) contains one and only one set of edges that forms a nontrivial circuit.

Graph with five vertices of degrees \(1,2,3,3\), and \(5 .\)

Draw all nonisomorphic simple graphs with four vertices.

Graph with four vertices of degrees \(1,2,3\), and \(3 .\)

Prove that matrix multiplication is associative: If \(\mathbf{A}, \mathbf{B}\), and C are any \(m \times k, k \times r\), and \(r \times n\) matrices, respectively, then \((\mathbf{A B}) \mathbf{C}=\mathbf{A}(\mathbf{B C})\),

Draw all nonisomorphic graphs with four vertices and no more than two edges.

In each of 8-21, either draw a graph with the given specifications or explain why no such graph exists. Graph, six vertices, five edges, not a tree

Prove that an edge \(e\) is contained in every spanning tree for a connected graph \(G\) if, and only if, removal of \(e\) disconnects \(G\).

Use mathematical induction to prove that if \(\mathbf{A}\) is any \(m \times m\) matrix, then \(\mathbf{A}^{n} \mathbf{A}=\mathbf{A} \mathbf{A}^{n}\) for all integers \(n \geq 1\). (You will need to use the result of exercise 16.)