CS 70 Discrete Mathematics and Probability Theory Fall 2019 Alistair Sinclair and Yun S. Song

CS 70 Discrete Mathematics and Probability Theory Fall 2019 Alistair Sinclair and Yun S. Song HW 3 Note:This homework consists of two parts. The rst part (questions 1-6) will be graded and will determine your score for this homework. The second part (questions 7-9) will be graded if you submit them, but will not affect your homework score in any way. You are strongly advised to attempt all the questions in the rst part. You should attempt the problems in the second part only if you are interested and have time to spare.

Part 1: Required Problems

• Degree Sequences

Thedegree sequenceof a graph is the sequence of the degrees of the vertices, arranged in descend- ing order, with repetitions as needed. For example, the degree sequence of the following graph is

(3;2;2;2;1).

For each of the parts below, determine if there exists a simple undirected graphG(i.e. a graph without self-loops and multiple-edges) having the given degree sequence. Justify your claim.(a)(3;3;2;2) (b)(3;2;2;2;2;1;1) (c)(6;2;2;2) (d)(4;4;3;2;1)

Solution:

(a)Yes The following graph has degree sequence(3;3;2;2).CS 70, Fall 2019, HW 31

(b)No For any graphG, the number of vertices that have odd degree is even. The given degree sequence has 3 odd degree vertices.(c)No The total number of vertices is 4. Hence there cannot be a vertex with degree 6.(d)No The total number of vertices is 5. Hence, any degree 4 vertex must have an edge with every other vertex. Since there are two degree 4 vertices, there cannot be a vertex with degree 1.

• Bipartite Graphs

An undirected graph is bipartite if its vertices can be partitioned into two disjoint setsL,Rsuch that each edge connects a vertex inLto a vertex inR(so there does not exist an edge that connects two vertices inLor two vertices inR).(a)Gis bipartite, withLandRbeing a bipartite partition of the vertices.Prove thatå v2L deg(v) =å v2R deg(v).(b)Gis bipartite, withLandRbeing a bipartite partition of the vertices. Let sandtdenote the average degree of vertices inLandRrespectively. Prove thats=t=jRj=jLj.(c) doubleof a graphGconsists of two copies ofGwith edges joining the corresponding “mirror” vertices. More precisely, ifG= (V;E), whereV=fv1;v2;:::;vngis the set of vertices andEthe set of edges, then the double of the graphGis given byG1= (V1;E1), where V1=fv1;v2;:::;vn;v

1;v

2;:::;v

ng; and E1=E[f(v

i;v

j)j(vi;vj)2Eg[f(vi;v

i);8ig:

Here is an example, CS 70, Fall 2019, HW 32

Draw the double of the following graph:(d)G1is a bipartite graph,G2is the double ofG1,G3is the double ofG2, and so on. (EachGi+1has twice as many vertices asGi). Show that8n1,Gnis bipartite.

Hint: Use induction on n.

Solution:

(a) Gis bipartite, each edge connects one vertex inLwith a vertex inR. Since each edge contributes equally toå v2L deg(v)andå v2R deg(v), we see that these two values must be equal.(b)å v2L deg(v) =å v2R deg(v). ThusjLj s=jRj t. A little algebra gives us the desired result.(c) CS 70, Fall 2019, HW 33

(d)P(n)be the proposition thatGnis bipartite. The base case is when n=1. We see thatP(1)must be true sinceG1is bipartite by assumption. Now suppose that fork1,P(k)holds. We see that the graphGk+1consists of two subgraphs, each having the same structure asGk, except the edges joining the corresponding vertices of the two subgraphs.Ignore these extra edges, i.e, the edges joining the corresponding vertices of the two subgraphs.SinceP(k)is true, we can label the two subgraphs into disjoint setsfL1;R1gandfL2;R2g.Then we can dene new setsL=fL1;R2gandR=fR1;L2gthat are disjoint. Every edge connects a vertex fromL1toR1and fromL2toR2, so it connects fromLtoR. Now considering the extra edges that we ignored, we see that each such edge connects a vertex fromL1to a vertex inL2and a vertex inR1to a vertex inR2. Hence, every edge connects fromLtoR.Thus, the graphGk+1is bipartite.

• Planarity and Graph Complements

LetG= (V;E)be an undirected graph. We dene the complement ofGasG= (V;E)where E=f(i;j)ji;j2V;i6=jgE; that is,Ghas the same set of vertices asG, but an edgeeexists isG if and only if it does not exist inG.(a) Ghasvvertices andeedges. How many edges doesGhave?(b)Gbeing planar implies thatGis non-planar.(c)Gwith at least 13 vertices, ifGis non-planar, thenGis planar. Construct a counterexample to show that the converse does not hold.Hint: Recall that if a graph contains a copy of K5, then it is non-planar. Can this fact be used to construct a counterexample?

Solution:

(a) Ghasvvertices, then there are a total of v(v1) 2 edges that could possibly exist in the graph.Sinceeof them appear inG, we know that the remaining v(v1) 2 emust appear inG.(b) Gis planar, we know thate3v6. Plugging this in to the answer from the previous part, we have thatGhas at least v(v1) 2 (3v6)edges. Sincevis at least 13, we have that v(v1) 2

v12 2 =6v, soGhas at least 6v3v+6=3v+6 edges. Since this is strictly more than the 3v6 edges allowed in a planar graph, we have thatGmust not be planar.CS 70, Fall 2019, HW 34