[PDF] Math 68 - Spring 2014 - Practice problems with solutions - Chapter 2





Previous PDF Next PDF



2 Trees

Further if T has exactly two leaf vertices



Discussion 4A

a vertex with degree 1. (a) Prove that every tree on n ? 2 vertices has at least two leaves. ... multiple longest paths then we just pick one of them).



Solutions to In-Class Problems — Week 4 Fri

of the degree-one vertices—to a new vertex lengthening the path by one. correct proof of the theorem “Every connected simple graph with two ends is ...



Math 68 - Spring 2014 - Practice problems with solutions - Chapter 2

paths; each of the new cycles is one of those two paths closed off by e. D. 2.1.18 Prove that every tree with maximum degree ? > 1 has at least ? leaves.



HOMEWORK 2 (1) Let G be a simple graph where the vertices

must be at least one vertex that has degree less than 2. (3) Prove that if a graph G has exactly two vertices u and v of odd degree then G has. a u



Recitation 10 Graph Theory Introduction to Graph Theory

Since G? is a graph each edge in E(G?) must be between two vertices Prove that



Recitation 9 Graph Theory Introduction to Graph Theory

Since G? is a graph each edge in E(G?) must be between two vertices Prove that



AMS 550.472/672: Graph Theory Homework Problems - Week III

suppose that every vertex has degree k where k is some natural number. Show that G where Pi is a path of length two for each i = 1



Chapter 6: Graph Theory

Conversely if there is one and only one path joining any two vertices of a graph





GRAPH THEORY { LECTURE 4: TREES - Department of Computer

Lemma 1 10 Let v and w be two vertices in a tree T such that w is of maximum distance from v (i e ecc(v) = d(v;w)) Then w is a leaf Proof Let P be the unique v-w path in tree T If deg(w) 2 then w would have a neighbor z whose distance from v would equal d(v;w) + 1 contradicting the premise that w is at maximum distance z w v T P



Graph Theory: Tree has at least 2 vertices of degree 1 - Mathematics

1 Prove that a tree with exactly two vertices of degree one is a path 2 Let G be a graph and de ne T(G) to be the number of subgraphs of G which are trees For instance T(K n) = nn 2;T(P n) = n (recall P n is the polygon of length n) and if G is not connected then T(G) = 0:



Chapter 111(?): Trees - University of California Berkeley

Every tree with at least 2 vertices has at least 2 vertices of degree 1 Every tree is bipartite Removing any edge from a tree will separate the tree into 2 connected components Molecules and Friends 1 (F) Show that C nH 2n+1OH has a tree structure (carbon makes 4 bonds hydrogen 1 and oxygen 2) The molecule is connected with 3n+3 vertices



Exercises for the course Graph Theory TATA64

(b) Prove that the endpoints of a longest path in a nontrivial (i e containing at least two vertices) tree both have degree one 1 33 (a) Show that if Gis a tree with ( G) k then Ghas at least kvertices of degree one (b) Deduce that every tree with exactly two vertices of degree one is a path 1 34 Let Gbe graph with jV(G)j 1 edges



CS173 Lecture B November 17 2015 - University of Illinois

Every treeT= (V;E) with at least two vertices has at leasttwo nodes that have degree 1 (hint: consider a longest path inthe tree) If a treeT= (V;E) has nvertices then it has n edges Every tree with at least two vertices has at least two leaves Theleavesof a tree are the nodes with degree 1; all other nodesareinternal nodes



DISCRETE MATHEMATICS 21228 — HOMEWORK 8 SOLUTIONS - CMU

two vertices of degree one A tree is connected so there are no vertices of degree zero Suppose for a contradiction that there are v vertices and v ?1 have degree at least two Then the sum of the degrees of the vertices is at least 1+2(v?1) = 2v?1 so the number of edges (which is always one half the sum of the degrees) is at least v

How to prove that every nontrivial tree has at least 2 vertices of degree 1?

Graph Theory: Tree has at least 2 vertices of degree 1. Prove that every nontrivial tree has at least 2 vertices of degree 1 by showing that the origin and terminus of a longest path in a nontrivial tree both have degree 1. Ok, so this statement is pretty obviously true, but I am having trouble proving it using graph theory language.

Is it possible to draw a tree with 5 vertices?

Is it possible to draw a tree with five vertices having degrees 1, 1, 2, 2, 4. Solution. Since the tree has 5 vertices hence it has 4 edges. Now given the vertices of tree are having degrees1, 1, 2, 2, 4.i.e., the sum of the degrees of the tree = 105By handshaking lemma, 2q = ? d (vi )i =1 Where q is the number of edges in the graph

How to find the sum of all the vertices of a tree?

Every tree has n ? 1 edges, so the the sum of the degrees of all the vertices of any tree have to be 2 ( n ? 1). But if there are fewer than two vertices of degree one, then the sum of the degrees of all the vertices must be at least 2 ( n ? 1) + 1, which is a contradiction.

How many edges does a tree have on n vertices?

Thus by theorem (which states that a tree on n vertices has n-1 edges), it should have 5-1=4 edges. By handshaking lemma, total degree of the tree (sum of degrees of all vertices) is 2 × (No. of edges) = 2 × 4 =8 This tree has 2 vertices each of degree 3 ? The sum of degrees of remaining 3 vertices is 8-3-3=2

Math 68 - Spring 2014 - Practice problems with solutions -

Chapter 2

2.1.2

Let Gbe a graph.

(a)Prove thatGis a tree if and only ifGis connected and every edge is a cut edge. Proof.Recall that an edge is a cut edge if an only if it is part of a cycle. Then every edge is a cut edge if and only ifGis acyclic. SinceGis a tree if and only ifGis connected and acyclic,Gis a tree if and only if it is connected and every edge is a cut edge. (b)Prove thatGis a tree if and only ifGis loopless andadd ingan yedge with endpoints inV(G)creates exactly one cycle. Proof.By Corollary 1.2.5, adding any edge to a tree produces a cycle. Now suppose adding any edgeeproduces a cycle. ThenGmust be connected (sinceeis not a cut edge ofG+e, and an edge with one endpoint in one component and the other in a separate component would be a cut edge). Now supposeGalready has a cycleC. Then adding an edgeewith both endpoints adds at least two cycles: the edge separates inCinto two paths; each of the new cycles is one of those two paths, closed o bye.

2.1.18

Pro vethat e verytree with maxim umdegree >1has at leastleaves. Show that this is the best possible by constructing ann-vertex tree with exactly leaves foe each choice ofn,withn >2. Proof.If = 0 or 1, thenG=P1orP2. Otherwise, pick a vertexvof degree . ThenGv contains all of the leaves ofG. It also has (at least) components since there is at most one path connecting any two of the vertices adjacent tov, which must be the path going through v. Each of those components has at least one leaf (or one isolated point) and is itself a tree. Sincevremoved (at most) one edge incident to each resulting component, each component has at least one leaf (or isolated vertex) which was also a leaf ofG. SoGhas at least leaves.

2.1.13

Pro vethat ev erygraph with diameter dhas an independent set with at least d(1 +d)=2evertices. Proof.Consider a path of minimal length between two verticesuandvwithd(u;v) =d. This path hasd+ 1 vertices, all with the property that if they are not adjacent in the path, then they are not adjacent inG. Then by alternating colors, one can two-color the vertices in the path. The set which includes one or both endpoints (the independent set of a single color) is of sizedd+ 1)=2e. 1 2

2.1.40

Let Gbe a tree withkleaves. Prove thatGis the union of pathsP1;:::;Pdk=2e such thatPi\Pj6=;for alli6=j. Proof.Consider a collection ofdk=2epathsfPigthat cover the leaves ofG. ConsiderP i`(Pi). Suppose that there are two pathsPi(with endpointsuiandvi) andPj(with endpointsuj andvj) which do not intersect. Then the pathsQifromuitovjandQjfromujtovitogether have all the same edges asPiandPj, together with the edges on a path which connectsPi toPj. So`(Pi) +`(Pj)< `(Qi) +`(Qj). Also, ifSdk=2e i=1does not coverG, then since it does cover the leaves,Sdk=2e i=1Pimust be disconnected, and therefore have some pair of paths which are disjoint.

Now take a collection ofdk=2ewhich maximizesP

i`(Pi) (such a thing exists becauseG is nite). Then by the above argument,Sdk=2e i=1PicoversGand each of the paths pairwise intersect.

2.1.44

Pro veor dispro ve:If a simple graph w ithdiameter 2 has a cut-v ertex,then its complement has an isolated vertex. Proof.Consider a vertexuwhich is not adjacent to every other vertex inV(G) (and therefore is not isolated inG). Letvbe a vertex which is not adjacent tou. We will show thatGu is connected (Gis connected because diam(G)<1). Leta2V(G)u. Then there is a path of length at most 2 fromatov. Sincevis not adjacent tou, that path cannot go throughu. Therefore that path is ana;vpath inGu. By transitivity, this implies thatGuis connected. Souis not cut.

2.1.47Diameter and radius

(a)Prove that the distance functiond(u;v)on pairs of vertices of a graph satises the triangle inequality:d(u;w)d(u;v) +d(v;w). Proof.Consider a pathPof minimal length fromutovand a path of minimal lengthQ fromvtow. Then there is a path fromutowinP[Qof length at most`(P) +`(Q). This may not be a minimal length path fromutow, but it does boundd(u;w) above byd(u;v) +d(v;w). (b)Use part (a) to prove thatdiam(G)2rad(G)for every graphG. Proof.Consider two anu verticesuandv, and letxbe an element of the center (so (x) = rad(G) is minimal). By (a), d(u;v)d(u;x) +d(v;x)(x) +(x) = 2rad(G): 3 (c)For all positive integersranddthat satisfyfd2r, construct a simple graph with radiusrand diameterd.(Hint: build a suitable graph with one cycle.) Consider the lollypop, a cycleC2rwith handlePdrattached at vertexx, withrd2r. Ifd=r, this is just the cycle, which has radius = diameter =r. By adding a path tox of length less or equal tor, the eccentricity ofxremain unchanged (the farthest vertex is still on the other side of the cycle). However, the end of the handle isdrfather away from the antipode ofx, and so isdr+r=daway fromx. Since anything closer in on the handle and anything closer in the cycle both have smaller eccentricities than

these two vertices,dis the new diameter.x= 3 + 4= 3 + 42.1.62Let Gbe a connected graph withnvertices. Dene a new graphG0having one

vertex for each spanning tree ofG, with vertices adjacent inG0if and only if the corresponding trees have exactlyn(G)2common edges. Prove thatG0is connected. Determine the diameter ofG0.(an example is given in the book) Proof.Consider two spanning treesTandT0ofG, and say the dier by 2medges. Letebe inTand not inT0. Then there is an edgee0ofT0not inTso thatT00=T0+ee0is also a spanning tree. SinceT0diers fromT00by 2m2, we can recursively generate a path inG0 fromTtoT0. Moreover, this path is length atmostm, so the diameter ofG0cannot be any greater than e(G)(n(G)1) becauseT0cannot dier fromTby more edges thanGE(T). Also, the diameter cannot be any larger thann(G)1 sincee(T) =e(T0) =n(G)1.

2.1.68

Can the graph b elowb edecomp osedin toedge-disjoin tspanning trees? In to

isomorphic edge-disjoint spanning trees?Yes!Y oucan start thinking ab outit this w ay:y ouha venine v ertices,s oan yspanning tree is

going to need 8 edges. Since there are 16 edges inG, there is some hope. In fact, you know that if you remove the edges of any spanning subgraph fromG, if you can manage to keep the result connected, what remains will be a spanning tree too! Next, since there are two vertices of degree 2, those had better be leaves in both of the disjoint spanning trees. A naive rst try, starting at one of those degree-two vertices and drawing a long path that ends at the other degree two vertex works! 4 To get two which are isomorphic, we're going to have to be better about exploiting the symmetry of the graph. I started with these two pictures:[

Then I tried to keep one the 180

rotation of the other:[

Result:

2.2.1

Determine whic htrees ha vePr uferco desthat

(a)contain only one value, Answer:The star (there is only one internal vertex). (b)contain exactly two values, Answer:A tree with two internal verticesu;v(they must be adjacent, andTuvis a star). 5 (c)have distinct values in all positions. Answer:The path (every vertex appearing in the list has degree 2, and there are exactly

2 missing).

2.2.8 Coun tthe follo wingsets of trees w iththe v ertexset [n], giving two proofs for each: one using the Prufer correspondence and one by direct counting arguments. (a)trees that have 2 leaves Answer:n!=2. (1) There are 2 leaves, so these are the lists withn2 distinct values. So pick two values not in the list (n

2ways), and how to rearrange then2 distinct values

in the list ((n2)! ways. Butn

2(n2)! =12

n(n1)(n2)! =12 n!. (2) These are paths, so there aren! ways of rearranging the vertices, which double-counts the re ection of the path. (b)trees that haven2leaves

Answer:

12 n(n1)2n2. (1) These are lists with exactly two values, since there are 2 non-leaves. Pick a rst value, then a second. Then for each element of the list of length n2, decide which of the two values it is. This will double count swapping the rst and second chosen values. (2) If there aren2 leaves, then there are 2 internal vertices. Put one on the left and one on the right. Then from the remaining vertices, decide whether they're adjacent to the left vertex or not (if not, they're adjacent to the right). Divide by two, since this double counts exactly the horizontal ip. 2.2.3 Let Gbe the graph below. Use the Matrix Tree Theorem to nd a matrix whose determinant is(G).1234 6

Answer:

D=0 B B@8 6 5 51
C

CAandA=0

B

B@0 4 1 3

4 0 2 0

1 2 0 2

3 0 2 01

C

CAsoQ=0

B

B@8413

4 62 0

12 52

3 02 51

C CA

So, for example

(G) = det0 @62 0 2 52 02 51 A = det0 @841 12 5 3 021 A =det0 @42 0 1 52 32 51
A = 106

2.2.10

Compute (K2;m). Also, compute the number of isomorphism classes of spanning trees ofK2;m.1234m0 m+ 1 Answer.Method 1:Since any spanning treeTmust be connected, there has to be some minimal path from 0 tom+ 1. SinceTis acyclic, there can only be one such path. Pick a vertex amongstf1;:::;mgfor the unique path to go through. For every other vertex, pick one edge (connecting to 0 orm+ 1). This givesm2m1spanning trees. Each one of the resulting trees looks like0m+1There aredm12 eisomorphism classes of these ([1 andm2 leaves]+[2 andm3 leaves]+). Method 2:Using the formula(G) =(Ge) +(Ge), the number of spanning trees of K

2;mis the same as the sum of the number of spanning trees for the two graphs

7

1234m0

m+ 11234m m+ 1 The one on the left has the same number of spanning trees atK2;m1. The one of the right simplies again to the sum of the number of spanning trees for the two graphs1234m m+ 1 1234m
Again, the graph on the left isK2;m1. The graph on the right is a anm-start with doubled edges. So (K2;m) = 2(K2;m1) + 2m1: Using induction, you can see thatn2n1satises this recursion relation. Fun fact: if you have a recursion relation that you can't seem to work out on your own, you can work out the rst few cases on your own and plug those rst few values into the Online Encyclopedia of Integer Sequences (http://oeis.org/). For example, whenm= 1,K2;1=P2. So (K2;1) = 1; (K2;2) = 21 + 21= 4; (K2;3) = 24 + 22= 12; (K2;4) = 212 + 23= 32; (K2;5) = 232 + 24= 80;:::

Try plugging in 1,4,12,32,80 into the OEIS.

To count isomorphism classes, notice that in the recursion, we're implying that at some step I'm taking a tree from a doubled star (where some pair of edges incident from the middle vertices are chosen for the tree { those were the contracted edges which caused the doubled star), and all other middle vertices were adjacent to exactly one of the vertices from the partite of size 2. See above.

2.2.23

Pro vethat if the G racefulT reeConjecture is true and Tis a tree withmedges, thenK2mdecomposes into2m1copies ofT.(Hint: Apply the cyclically invariant decom- position ofK2m1for trees withm1 edges from the proof of Theorem 2.2.16.) 8 Proof.LetT0=Tvwherevis some leaf ofv. Decompose the complete graphGon [2m1] into 2m1 copies ofT0. Each vertex inGis represented by the neighbor ofvinTexactly once in this decomposition, so the complete graph on [2m] can be built by adding one edge from that neighbor to vertex 2mfor each copy ofT0. This presents a decomposition ofK2m into 2m1 copies ofT.

2.2.31

An up-down labelingis a graceful labeling for which there exists a critical value such that every edge joins vertices with labels above and below. Prove that ecery caterpillar has an up-down labeling. Prove that the 7-vertex tree that is not a caterpillar has no up-down labeling.

Proof.

(1) Caterpillars have up-down labelings.Order the vertices of the spine (vertebrae) from left to right, noting that the endpoints are leaves. We'll show that there's an up-down labeling so that the right-most vertebrae is labeled with a 0, by induction on the numberk of vertebrae. Base case:Ifk= 2, the caterpillar isP2, which trivially has up-down labeling with=12

Put the 0 on the right.

Induction hypothesis:Any caterpillar with spine of lengthkhas an up-down labeling with the right-most vertex labeled with 0. Induction step:LetGbe a caterpillar with spine of lengthk+1. Consider the second to last vertebrae on the rightv, and letG0be the subgraph induced by deleting all of the leaves adjacent tov(except possibly one ifGis a star).G0is a caterpillar with spine of lengthk, so by the induction hypothesis has an up-down labeling with a 0 onv; let0be the critical value of that labeling. Now labelGas follows: (a) lab elthe deleted lea veswith 0 ;1;:::;d(v)2 (there ared(v)1 leaves), and (b) for ev eryv ertexof Galso inG0, ifa0is the label inG0, replace with the labela= n(G)1a0.

For example,

G

0!G78490

65321548312

67910110

12

0= 7:5= 4:5

nquotesdbs_dbs17.pdfusesText_23
[PDF] show that f is continuous on (?? ?)

[PDF] show that for each n 1 the language bn is regular

[PDF] show that if a and b are integers with a ? b mod n then f(a ? f(b mod n))

[PDF] show that if an and bn are convergent series of nonnegative numbers then ? anbn converges

[PDF] show that if f is integrable on [a

[PDF] show that if lim sn

[PDF] show that p ? q and p ? q are logically equivalent slader

[PDF] show that p ? q and p ? q ? p ? q are logically equivalent

[PDF] show that p(4 2) is equidistant

[PDF] show that p2 will leave a remainder 1

[PDF] show that the class of context free languages is closed under the regular operations

[PDF] show that the class of turing recognizable languages is closed under star

[PDF] show that the family of context free languages is not closed under difference

[PDF] show that the language l an n is a multiple of three but not a multiple of 5 is regular

[PDF] show that x is a cauchy sequence