Math 344: Introduction to Combinatorics

Comments on Homework: Section 1.3

Problem 1

Question

For part (c), I get that a graph with 20 edges and all vertices of the same degree can have either:

1. 40 vertices, each of degree 1, or
2. 20 vertices, each of degree 2, or
3. 10 vertices, each of degree 4

Is this right?

Answer

There's another possibility. (Also, the answer is in the back of the book if you want to check.)

Problem 2

Question

Could you please give me some hint to solve this problem?

Answer

Let's look at part (a): ``Must the number of people at a party who do not know an odd number of people be even?'' How can we model this as a graph model? One simple way is by:

• vertex = person (that is, one vertex for each person at the party)
• edge = the two people (vertices) do not know each other.

Now the question is: ``Must the number of vertices of odd degree (=connected to an odd number of other people) be even?'' Hopefully the section will allow you to answer this question.

When in doubt, you can also start playing: can you have a party with (say) 3 people that has an odd number of people, each of whom don't know an odd number of others? Perhaps by playing with simple examples you'll see what's happening.

Question

In part (d), the wording of the question is a bit ambiguous. By ``let s(x) denote the number of vertices adjacent to at least one of x's neighbors'', does it mean that s(x) is the number of vertices (not including any of x's neighbors and not counting any vertex more than once) adjacent to one or more of x's neighbors?

Answer

No, they mean that s(x) = number of vertices (including x and any of x's neighbors, but not counting any vertex more than once) adjacent to one or more of x's neighbors. Why would you exclude the neighbors themselves?

Question

For part (d), do we include the vertex x itself when calculating s(x)?

Answer

Yes.

Question

It seems obvious for part (d) that the answer is no. Just making a graph with an edge from A to B and another from B to C, gives s(A)=s(C)=2 and s(B)=1. It won't be true in the specific case either since I get s(a)=s(b)=s(c) =s(d)=5, s(e)=4, s(f)=3, s(g)=2.

Answer

I think you're right.

Question

I think the numbers are wrong for 1.3 #2 (d) on the web page.

I get s(a) = 5, s(b) = 6, s(c) = 5, s(d) = 6, s(e) = 7, s(f) = 5, and s(g) = 3. For example, e has neighbors b,f, and d. g is adjacent to f, a is adjacent to b and d, and c is adjacent to b and d as well. That's all 7 of them (including e).

Answer

Um, start over. I agree with ``e has neighbors b,f, and d.'' But let's look at the rest:

• adjacent to b: a, c, e
• adjacent to f: e, g
• adjacent to d: a, c, e

So:

• adjacent to a neighbor of e: a, c, e, g

or s(e) = 4. Is this wrong?

Problem 11

Question

I get that only graphs (a) and (b) are not bipartite. Is this right?

Answer

Yes.