Question 1

Draw a directed graph with the following adjacency matrix:

Accepted Answer

The answer of Draw a directed graph with the following...

Question 2

A certain graph has 19 vertices, 16 edges, and no circuits. Is it connected? Explain.

Accepted Answer

No. The graph is not connected because if it were connected, then, since it is circuit-free, it would be a tree and would have 18 edges instead of 19 edges.

Question 3

a. Prove that having n vertices, where n is a positive integer, is an invariant for graph
isomorphism.
b. Prove that having a vertex of degree 3 is an invariant for graph isomorphism.

Accepted Answer

a. Proof:
Suppose $ G $ and $ G^{\prime} $ are isomorphic graphs and suppose $ G $ has $ n $ vertices, where $ n $ is a positive integer. By definition of graph isomorphism, there is a one-to-one correspondence $ h: V(G) \rightarrow V(G $ But $ V(G) $ is a finite set and two finite sets in one-to-one correspondence have the same number of elements. Therefore, there are as many edges in $ V\left(G^{\prime}\right) $ as there are in $ V(G) $, and so $ G $ and $ G^{\prime} $ have the same number of edges.
b. Proof:
Suppose $ G $ and $ G^{\prime} $ are isomorphic graphs and suppose $ G $ has a vertex $ v_{0} $ of degree 3 . [We must show that $ G^{\prime} $ has a vertex of degree 3.] By definition of graph isomorphism, there are one-toone correspondences $ g: V(G) \rightarrow V\left(G^{\prime}\right) $ and $ h: E(G) \rightarrow E\left(G^{\prime}\right) $ that preserve the edge-endpoint functions in the sense that for all $ v $ in $ V(G) $ and $ e $ in $ E(G), v $ is an endpoint of $ e \Leftrightarrow g(v) $ is an endpoint of $ h(e) $. Let $ e_{1}, e_{2}, \ldots, e_{m} $ be the $ m $ distinct edges that are incident on $ v_{0} $, noting that $ m=2 $ or $ m=3 $ because $ v_{0} $ has degree 3 . Then $ h\left(e_{1}\right), h\left(e_{2}\right), \ldots, h\left(e_{m}\right) $ are the $ m $ distinct edges that are incident on $ g\left(v_{0}\right) $ in $ G^{\prime} $. [The reason why $ h\left(e_{1}\right), h\left(e_{2}\right), \ldots, h\left(e_{m}\right) $ are distinct is that $ h $ is one-to-one and $ e_{1}, e_{2}, \ldots, e_{m} $ are distinct. And the reason why $ h\left(e_{1}\right), h\left(e_{2}\right), \ldots, h\left(e_{m}\right) $ are incident on $ g\left(v_{0}\right) $ is that $ g $ and $ h $ preserve the edge-endpoint functions of $ G $ and $ G^{\prime} $ and $ e_{1}, e_{2}, \ldots, e_{m} $ are incident on $ v_{0} . J $ Also, there are no edges incident on $ g\left(v_{0}\right) $ other than the ones that are images under $ g $ of edges incident on $ v $ because $ g $ is onto and $ g $ and h preserve the edge-endpoint functions of $ G $ and $ \left.G^{\prime}\right] $. Thus the number of edges incident on $ v_{0} $ equals the number of edges incident on $ g\left(v_{0}\right) $. Finally, an edge $ e $ is a loop at $ v_{0} $ if, and only if, $ h(e) $ is a loop at $ g\left(v_{0}\right) $, so the number of loops incident on $ v_{0} $ equals the number of loops incident on $ g\left(v_{0}\right) $. [For since $ g $ and $ h $ preserve the edge-endpoint functions of $ G $ and $ G^{\prime}, v_{0} $ is an endpoint of $ e $ in $ G $ if, and only if, $ g\left(v_{0}\right) $ is an endpoint of $ h(e) $ in $ G^{\prime} $. It follows that $ v_{0} $ is the only endpoint of e in $ G $ if, and only if, $ g\left(v_{0}\right) $ is the only endpoint of $ h(e) $ in $ G^{\prime} $.] Now the degree of $ v_{0} $, which is 3 , equals the number of edges incident on $ v_{0} $ plus the number of edges incident on $ v_{0} $ that are loops (since a loop contributes 2 to the degree of $ \left.v_{0}\right) $. But we have already shown that the number of edges incident on $ v_{0} $ equals the number of edges incident on $ g\left(v_{0}\right) $ and that the number of loops incident on $ v_{0} $ equals the number of loops incident on $ g\left(v_{0}\right) $. Hence $ g\left(v_{0}\right) $ also has degree 3 . Note: An alternative proof for this problem could consider two cases separately. In one case the vertex v0 in G of degree 3 would have three distinct edges incident on it, and in the other case there would be one edge and one loop incident on it.

Question 4

Determine whether each of the following graphs has an Euler circuit. If it does have an Euler circuit, ﬁnd such a circuit. If it does not have an Euler circuit, explain why you can be 100% sure that it does not.

Accepted Answer

The answer of Determine whether each of the following graphs...

Question 5

Find the following matrix product: $$\left[ \begin{array} { l l } 
2 & 0 \
0 & 1 \
3 & 2
\end{array} \right] \left[ \begin{array} { l l l } 
1 & 3 & 0 \
2 & 4 & 2
\end{array} \right]$$

Accepted Answer

The answer of Find the following matrix product: \[\left[ \begin{array}...

Question 6

Determine whether any two of the simple graphs $G _ { 1 } , G _ { 2 }$, and $G _ { 3 }$ are isomorphic. If they are, give a vertex function that defines the isomorphism. If they are not, give an isomorphic invariant that they do not share.

Accepted Answer

The answer of Determine whether any two of the simple...

Question 7

For each of (a)-(c) below, either draw a graph with the speciﬁed properties or else explain why no such graph exists.
(a) Graph with six vertices of degrees 1, 1, 2, 2, 2, and 3.
(b) Graph with four vertices of degrees 1, 2, 2, and 5.
(c) Simple graph with four vertices of degrees 1, 1, 1, and 5.

Accepted Answer

The answer of For each of (a)-(c) below, either draw...

Question 8

Either draw a graph with the given speciﬁcation or explain why no such graph exists.
(a) full binary tree with 16 vertices of which 6 are internal vertices
(b) binary tree, height 3, 9 vertices
(c) binary tree, height 4, 18 terminal vertices

Accepted Answer

The answer of Either draw a graph with the given...

Question 9

Consider the adjacency matrix for a graph that is shown below. Answer the following questions by examining the matrix and its powers only, not by drawing the graph. Show your work in a way that makes your reasoning clear.  
 (a) How many walks of length 2 are there from $v _ { 1 }$ to $v _ { 2 }$ ?
(b) How many walks of length 2 are there from $v _ { 1 }$ to $v _ { 3 }$ ?
(c) How many walks of length 2 are there from $v _ { 2 }$ to $v _ { 2 }$ ?

Accepted Answer

The answer of Consider the adjacency matrix for a graph...

Question 10

Determine whether each of the following graphs has a Hamiltonian circuit. If it does have an Hamiltonian circuit, ﬁnd such a circuit. If it does not have an Hamiltonian circuit, explain why you can be 100% sure that it does not.

Accepted Answer

The answer of Determine whether each of the following graphs...

Question 11

A certain connected graph has 68 vertices and 72 edges. Does it have a circuit? Explain.

Accepted Answer

The answer of A certain connected graph has 68 vertices...

Question 12

Determine whether any two of $G _ { 1 } , G _ { 2 }$, and $G _ { 3 }$ are isomorphic. If they are, give vertex and edge functions that define the isomorphism. If they are not, give an isomorphic invariant that they do not share.

Accepted Answer

The answer of Determine whether any two of \(G _...

Question 13

If a graph has vertices of degrees 1, 1, 2, 3, and 3, how many edges does it have? Why?

Accepted Answer

The answer of If a graph has vertices of degrees...

Question 14

$\text { Consider the following weighted graph: }$

(a) Use Kruskal's algorithm to ﬁnd a minimum spanning tree for the graph, and indicate the
order in which edges are added to form the tree.
(b) Use Prim's algorithm starting with vertex a to ﬁnd a minimum spanning tree for the
graph, and indicate the order in which edges are added to form the tree.
(c) Use Dijkstra's algorithm to ﬁnd the shortest path from a to

Accepted Answer

The answer of \(\text { Consider the following weighted graph:...

Quiz 10: Graphs and Trees

Draw a directed graph with the following adjacency matrix:

A certain graph has 19 vertices, 16 edges, and no circuits. Is it connected? Explain.

a. Prove that having n vertices, where n is a positive integer, is an invariant for graph isomorphism. b. Prove that having a vertex of degree 3 is an invariant for graph isomorphism.

Determine whether each of the following graphs has an Euler circuit. If it does have an Euler circuit, ﬁnd such a circuit. If it does not have an Euler circuit, explain why you can be 100% sure that it does not.

Find the following matrix product: $\left[ \begin{array} { l l } 2 & 0 \\0 & 1 \\3 & 2\end{array} \right] \left[ \begin{array} { l l l } 1 & 3 & 0 \\2 & 4 & 2\end{array} \right]$

For each of (a)-(c) below, either draw a graph with the speciﬁed properties or else explain why no such graph exists. (a) Graph with six vertices of degrees 1, 1, 2, 2, 2, and 3. (b) Graph with four vertices of degrees 1, 2, 2, and 5. (c) Simple graph with four vertices of degrees 1, 1, 1, and 5.

Either draw a graph with the given speciﬁcation or explain why no such graph exists. (a) full binary tree with 16 vertices of which 6 are internal vertices (b) binary tree, height 3, 9 vertices (c) binary tree, height 4, 18 terminal vertices

Determine whether each of the following graphs has a Hamiltonian circuit. If it does have an Hamiltonian circuit, ﬁnd such a circuit. If it does not have an Hamiltonian circuit, explain why you can be 100% sure that it does not.

A certain connected graph has 68 vertices and 72 edges. Does it have a circuit? Explain.

If a graph has vertices of degrees 1, 1, 2, 3, and 3, how many edges does it have? Why?

Quiz 10: Graphs and Trees

Draw a directed graph with the following adjacency matrix:

A certain graph has 19 vertices, 16 edges, and no circuits. Is it connected? Explain.

a. Prove that having n vertices, where n is a positive integer, is an invariant for graph isomorphism. b. Prove that having a vertex of degree 3 is an invariant for graph isomorphism.

Determine whether each of the following graphs has an Euler circuit. If it does have an Euler circuit, ﬁnd such a circuit. If it does not have an Euler circuit, explain why you can be 100% sure that it does not.

Find the following matrix product: [200132][130242]\left[ \begin{array} { l l } 2 & 0 \\0 & 1 \\3 & 2\end{array} \right] \left[ \begin{array} { l l l } 1 & 3 & 0 \\2 & 4 & 2\end{array} \right]​203​012​​[12​34​02​]

Determine whether any two of the simple graphs G1,G2G _ { 1 } , G _ { 2 }G1​,G2​ , and G3G _ { 3 }G3​ are isomorphic. If they are, give a vertex function that defines the isomorphism. If they are not, give an isomorphic invariant that they do not share.

For each of (a)-(c) below, either draw a graph with the speciﬁed properties or else explain why no such graph exists. (a) Graph with six vertices of degrees 1, 1, 2, 2, 2, and 3. (b) Graph with four vertices of degrees 1, 2, 2, and 5. (c) Simple graph with four vertices of degrees 1, 1, 1, and 5.

Either draw a graph with the given speciﬁcation or explain why no such graph exists. (a) full binary tree with 16 vertices of which 6 are internal vertices (b) binary tree, height 3, 9 vertices (c) binary tree, height 4, 18 terminal vertices

Determine whether each of the following graphs has a Hamiltonian circuit. If it does have an Hamiltonian circuit, ﬁnd such a circuit. If it does not have an Hamiltonian circuit, explain why you can be 100% sure that it does not.

A certain connected graph has 68 vertices and 72 edges. Does it have a circuit? Explain.

Determine whether any two of G1,G2G _ { 1 } , G _ { 2 }G1​,G2​ , and G3G _ { 3 }G3​ are isomorphic. If they are, give vertex and edge functions that define the isomorphism. If they are not, give an isomorphic invariant that they do not share.

If a graph has vertices of degrees 1, 1, 2, 3, and 3, how many edges does it have? Why?

Find the following matrix product: $\left[ \begin{array} { l l } 2 & 0 \\0 & 1 \\3 & 2\end{array} \right] \left[ \begin{array} { l l l } 1 & 3 & 0 \\2 & 4 & 2\end{array} \right]$