Weekly Summary, Week 6, Chapter 11/part a Name:

Due on Sunday, October 7, by midnight.

Type your answers under the questions given below, or, print out this sheet, use pen or pencil to fill it out, and email a scan or photo of it to the instructor.

1) How many subgraphs of K8 have 4 vertices? In answering this question (as in 11.2 #16) consider all vertices to be labeled. So if two subgraphs are isomorphic but have different vertices, consider them distinct. Set up the answer, do not reduce it.

2) If G has a degree sequence of (5, 4, 4, 4, 3, 2, 2, 2, 2, 1, 1) what is the degree sequence of

image1.wmfG

?[Hint: No need to draw the graph. It is an easy calculation, done for each vertex. Just think about how the degree of a vertex in G is related to its degree in

image2.wmfG

.] [See notes 11.1 for definition of degree sequence.]3) Let a graph G = (V, E) be defined as follows: Let S = {a, b, c, d, e, f}. Let V be the set of all 3-element subsets of S. Two vertices are adjacent if and only if they share exactly two elements in common. So for example the vertex {a, b, c} is adjacent to the vertex {a, b, d}. However, {a, b, c} is not adjacent to {a, d, e}.

a) How many vertices are in G?

b) What is the degree of each vertex?

c) How many edges are in G?

4) The two graphs given below are in fact isomorphic. Show the isomorphism. In other words assign each vertex in the first graph to a vertex in the second graph in such a way that edges match up with edges. An example, though a wrong answer, would be: a -1, b – 2, c – 3, d – 4, e – 5, f – 6.

image3.jpg

5) Are the following graphs isomorphic? [Hint: two graphs are isomorphic if and only if their complements are isomorphic.]

image4.png

6) How many non-isomorphic loop-free graphs with 6 vertices and 5 edges are possible? [NO multi-graphs]

[Note: you may want to provide a picture of the graphs that you came up with, so that if you get the number wrong, I can still give you some credit.]

bonus: If G is a loop-free undirected graph with 60 edges, and

image5.wmfG

has 30 edges, how many vertices does G have?

_1365528345.unknown

_1599993215.unknown