CS 103X: Discrete Structures Homework Assignment 8 — …

1 CS 103X: Discrete StructuresHomework Assignment 8 SolutionsExercise 1(10 points).The complement of a graphG= (V,E) is the graph(V,{{x,y}:x,y V,x6=y}\E).A graph isself-complementaryif it is isomorphic to its complement.(a)Prove that no simple graph with two or three vertices is self-complementary, without enumer-ating all isomorphisms of such simple graphs.(b)Find examples of self-complementary simple graphs with 4 and 5 (a)Obviously, two isomorphic graphs must have the same number of edges. Thus for a graphwithnvertices to be self-complementary, the total number ofpossibleedges,(n2), must beeven so that the graph and its complement can have the same number of edges.

2 (22)= 1 and(32)= 3, so no graph with 2 or 3 vertices can be self-complementary.(b)Here are the examples (top row) with their complements (bottom row). Convince yourself(with a bit of wire if necessary) that the pentagon and the five-pointed star are indeed 2(10 points).Prove that if a graph has at mostmvertices of degree at mostnand allother vertices have degree of at mostk, withk<nandm<n, then the graph is colorable withm+k+ 1 consider the reduced problem of coloring the graph minus themvertices of degreeat mostnand all edges involving those vertices . From the lecture notes, since all remaining verticeshave degreekor less,k+1 colors are enough for this reduced graph.

3 Then if we restore the originalgraph and assign one color not used to each of themvertices, the resulting graph will be coloredusingm+k+ 1 3(30 points).Prove or disprove, for a graphGon a finite set ofnvertices:(a)If every vertex ofGhas degree 2, thenGcontains a cycle.(b)IfGis disconnected, then its complement is connected.(c)IfTis a non-cyclic tour inG, and no strictly longer tour inGcontainsT, then both endpointsofThave odd (a)True. Assume, for contradiction, thatGhas no cycle, and consider the longest pathPinG(one must exist, since the graph is finite). Letvbe the final vertex inP sincevhas degree2, it must have two edgese1ande2incident on it, of which one, saye1, is the last edge of thepathP.

4 Thene2cannot be incident on any other vertex ofPsince that would create a cycle(v,e2,[section of P ending ine1],v). Soe2and its other endpoint are not part ofP, and canbe appended toPto give a strictly longer path, which contradicts our choice ofP. HenceGmust contain a cycle.(b)True. LetG denote the complement ofG. Consider any two verticesu,vinG. Ifuandvarein different connected components inG, then no edge ofGconnects them, so there will be anedge{u,v}inG . Ifuandvare in the same connected component inG, then consider anyvertexwin adifferentconnected component (sinceGis disconnected, there must be at leastone other connected component).

5 By our first argument, the edges{u,w}and{v,w}exist inG , souandvare connected by the path (u,w,v). Hence any two vertices are connected inG , so the whole graph is connected.(c)True. This is similar to Theorem for Eulerian tours. At each vertex of the tourT, labelthe incident edges as entering or leaving as in the lecture notes. At each endpoint of thetour, there is one leaving edge for every entering edge, except for exactly one edge (since thetour is non-cyclic) which is either leaving (if the vertex is the first one of the tour) or entering(if the vertex is the last one). This means an odd number of edges of the tour are incidentat each endpoint.

6 Assume, for contradiction, that an endpoint has even degree since thetour contributes an odd number of edges to this count, there must be at least one non-touredge incident at this vertex. This edge can be added toTto give a strictly longer tour thatcontainsT, which is a contradiction. Hence both endpoints ofThave odd 4(15 points).ConsidermgraphsG1= (V1,E1),G2= (V2,E2),..,Gm= (Vm,Em).Their union can be defined asm i=1Gi=(m i=1Vi,m i=1Ei).Show that, for any natural numbern 2, the cliqueKncan be expressed as the union ofkbipartitegraphs ifn proceed by induction onk. Fork= 1, there are two cliques:K1is just a singlepoint, which is trivially a bipartite also a single bipartite graph (each vertex in its owngroup).

7 Now, for the inductive step assume the claim holds fork=m. Now for anyn 2m+1, leta=bn2candb=dn2e, and divide the vertices ofKninto disjoint setsA,Bwith|A|=aand|B|= can define a bipartite graphGwith verticesA Band edgesv,wwithv A,w B. Removingall of these edges fromKnleave two cliquesKaandKb. Sincea,b 2m, each of these cliques canbe represented as a union ofmbipartite graphs. Since the two cliques have disjoint vertex sets, wecan say that the union of a bipartite graph over the vertices ofKaand a bipartite graph over thevertices ofKbwill still be a bipartite graph. Thus the two cliques together can be represented asthe union ofmbipartite graphs, and addingGto the union represents all ofKnasm+ 1 bipartitegraphs.

8 This completes the inductive step and thus by induction the property holds for 5(15 points).A binary tree is defined inductively as follows: A single vertexudefines a binary tree with rootu. A vertexulinked by edges to the roots of one or two binary trees defines a binary tree following figure illustrates the three possibilities:T1andT2are calledsubtrees,uis theparentof the roots of the subtrees, and these roots arechildrenofu. The vertices of a binary tree without any children are calledleaves. Here s an example of abinary tree:Thedistancebetween two vertices of a tree is the number of edges in the shortest path connectingthem.

9 Theheightof the tree is the maximum distance between the root and a leaf. Prove that theheight of a binary tree withnvertices is at leastblog2nc. (Hint: use the strong induction principle.)3 SolutionThe result follows from strong induction onn. The base case is the binary tree with onevertex, which is just the vertex itself. Obviously, this has height 0 =blog21c, so the base case assume the result holds for all binary trees with at mostmvertices, and consider a binary treewithn=m+ 1 vertices . By definition, this can be viewed as a root vertexuplus two subtreesT1andT2 evidentlyT1andT2together containmvertices.

10 Assume thatT1haspvertices thenT2hasm pvertices. Since bothpandm pare at mostm, the induction hypothesis applies andthe heights of the subtrees are at leastblog2pcandblog2(m p)crespectively. The heighthof theoriginal tree is one more than the height of the taller subtree (because of the edge linking theroot of the subtree to the root of the original tree), so we haveh= 1 + max{blog2pc,blog2(m p)c}Now at least one of the subtrees must have at leastdm2evertices, so we can writeh 1 + log2 m2 Ifmis odd, then this givesh 1 + log2m+ 12 = 1 +blog2(m+ 1) log22c= 1 +blog2(m+ 1) 1c= 1 +blog2(m+ 1)c 1=blog2(m+ 1)cAlso, ifmis even, then we haveh 1 + log2m2 1 +blog2m log22c 1 +blog2m 1c 1 +blog2mc 1 blog2mcBut sincemis even,blog2mc=blog2(m+1)