91Ó°ÊÓ

Find directed graphs that have the following adjacency matrices: a. \(\left[\begin{array}{llll}1 & 0 & 1 & 2 \\ 0 & 0 & 1 & 0 \\ 0 & 2 & 1 & 1 \\\ 0 & 1 & 1 & 0\end{array}\right] \quad\) b. \(\left[\begin{array}{llll}0 & 1 & 0 & 0 \\ 2 & 0 & 1 & 0 \\ 1 & 2 & 1 & 0 \\ 0 & 0 & 1 & 0\end{array}\right]\)

What is the total degree of a tree with \(n\) vertices? Why?

Find graphs that have the following adjacency matrices. a. \(\left[\begin{array}{lll}1 & 0 & 1 \\ 0 & 1 & 2 \\ 1 & 2 & 0\end{array}\right] \quad\) b. \(\left[\begin{array}{lll}0 & 2 & 0 \\ 2 & 1 & 0 \\\ 0 & 0 & 1\end{array}\right]\)

The following are adjacency matrices for graphs. In each case determine whether the graph is connected by analyzing the matrix without drawing the graph. a. \(\left[\begin{array}{lll}0 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 0\end{array}\right]\) b. \(\left[\begin{array}{llll}0 & 2 & 0 & 0 \\ 2 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 \\\ 0 & 0 & 1 & 1\end{array}\right]\)

Given any positive integer \(n\), (a) find a connected graph with \(n\) edges such that removal of just one edge disconnects the graph; (b) find a connected graph with \(n\) edges that cannot be disconnected by the removal of any single edge.

(i) Find all edges that are incident on \(v_{1}\). (ii) Find all vertices that are adjacent to \(v_{3}\). (iii) Find all edges that are adjacent to \(e_{1}\). (iv) Find all loops. (v) Find all parallel edges. (vi) Find all isolated vertices. (vii) Find the degree of \(v_{3 .}\) (viii) Find the total degree of the graph.

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

The solution for Example 11.2.5 shows a graph for which every vertex has even degree but which does not have an Euler circuit. Give another example of a graph satisfying these properties.

Prove part (2) of Proposition 11.6.1: Any two spanning trees for a graph have the same number of edges.

Given any two distinct vertices of a tree, there exists a unique path from one to the other. a. Give an informal justification for the above statement. b. Write a formal proof of the above statement.