Math 3345 Test # 3 Problems 1-3 are true/false.

1. If graph G is isomorphic to graph H, and if G has exactly 5 vertices of index 4, then H must also have exactly 5 vertices of index 4.

2. A graph is a tree if and only if the graph has n vertices and n-1 edges for some positive integer n.

3. Every connected graph has a spanning tree.

4. Give two of the isomorphism invariants of the pictured graph.

5. Either draw a graph with the specified properties or explain why it can't exist.

a) A simple graph with 5 vertices of degrees 2, 3, 3, 3, 5.

b) A graph with 4 vertices of degrees 4, 5, 7, 9.

c) A graph with 5 vertices and total degree 8.

d) A graph with 7 vertices and 6 edges that is not a tree.

e) A tree with 6 vertices, each of degree 2.

6 Determine whether the graphs are isomorphic. If the graphs are isomorphic, indicate corresponding vertices given by an isomorphism of the graphs.

7. Draw all nonisomorphic simple graphs with 4 vertices.

8. In a group of 15 people, is it possible for each person to have exactly 3 friends among the other people of the group? Assume that friendship is a symmetric relation. Explain the reasoning for your answer.

9. Recall that a complete graph is a simple graph for which each pair of vertices has exactly one edge.

a) How many edges does a complete graph with 12 vertices have?

b) How many nonisomorphic complete graphs with 10 vertices are there?

10. S is a relation from A = {1, 2, 3} to B = {4, 5, 6} given by S = {(1,5), (2,5), (3,4), (1,4)} .

a) Give the inverse relation.

b) Is S a function? Why or why not?

11. Define a relation G on by aGb if a b+1.

a) Is (5,2) G?    b) Is (6,5) G?     c) Is 3G7?

d) Draw the graph of G in the Cartesian plane.

12. Find 2 binary relations from {a, b} to {1, 2} that are not functions.

13. Let X be any non-empty set, and let P(X) be the power set of X. Define the relation S on P(X) by

A S B if A B.

Is S reflexive, symmetric, transitive? Justify your answers.

14. For this graph, either describe and Euler circuit that starts and ends at vertex a or say why an Euler circuit does not exist.

15. What is the difference between a circuit and a simple circuit?