502
Graphs and Trees
20.
2
1
5
6
7
8
3
4
(a)
(b)
a
h
b
f
g
c
d
e
21. Prove that two graphs are not isomorphic if one of them
a. has more nodes than the other.
b. has more arcs than the other.
c. has parallel arcs and the other does not.
d. has a loop and the other does not.
e. has a node of degree k and the other does not.
f. is connected and the other is not.
g. has a cycle and the other does not.
22. Draw all the nonisomorphic, simple graphs with two nodes.
23. Draw all the nonisomorphic, simple graphs with three nodes.
24. Draw all the nonisomorphic, simple graphs with four nodes.
25. Find an expression for the number of arcs in K n and prove that your expression is correct.
26. Verify Euler’s formula for the following simple, connected, planar graph.
27. Prove that K 2,3 is a planar graph.
28. Prove that the following graph is a planar graph.
29. If a simple, connected, planar graph has six nodes, all of degree 3, into how many regions does it divide
the plane?