## Description

Question 1: Find a Nonisomorphic Graph

Take a look at the following simple graph G:

a) Draw another graph H that has the same number of vertices and edges and the same

degrees as G but is not isomorphic to G.

b) Is there another invariant we discussed besides the number of vertices and edges and

the degrees, such as the length of circuits and paths, that could be used to show that G

and H are nonisomorphic? If so, please state how this invariant differs between the

two graphs.

Question 2: … And More about Graphs

a) In class we showed that the cycle C6 is bipartite. Which of the cycles C3, C4, C5, and

C7 are bipartite as well?

b) Bonus: Based on (a) there seems to be a rule that tells us for which numbers n the

cycle Cn is bipartite. What is that rule? Give an argument for this rule to be correct for

all integers n > 2.

c) How many nonisomorphic subgraphs does C4 have? Draw them.

d) Develop an equation for computing the number of edges |En| for any wheel Wn.

Explain your reasoning and test your equation by computing |E3|.

Question 3: Dijkstra in Action

Use Dijkstra’s algorithm to compute the shortest path from A to I, where edge labels

indicate the distance (or cost) between vertices. For each iteration, write down the

shortest path (i.e., its length and the vertices in it) from A to each vertex that has been

found so far, and also indicate which vertices are currently in the set S.

Question 4: Trees

a) How many vertices does a full 4-ary tree with 100 internal vertices have?

b) How many vertices and how many leaves does a complete m-ary tree of height h

have?

c) Build a binary search tree for the words the, final, exam, will, contain, at, least, one,

question, about, and trees using alphabetical order and adding words in the same

order as listed here.

d) Represent the expressions (x + x⋅y) + (x/y) and x + ((x⋅y + x)/y) using two binary trees.

e) How many non-isomorphic trees with four vertices are there? Draw them.

f) Bonus: Show that a full m-ary tree with l leaves has (l – 1)/(m – 1) internal vertices.

A

B

C

D

E

F

G

H

I

1

3

7

1

2

1

2

1

6

4

9 8