This Is Not a Tree This Is Not a Baby

\(\renewcommand{\d}{\displaystyle} \newcommand{\N}{\mathbb N} \newcommand{\B}{\mathbf B} \newcommand{\Z}{\mathbb Z} \newcommand{\Q}{\mathbb Q} \newcommand{\R}{\mathbb R} \newcommand{\C}{\mathbb C} \newcommand{\U}{\mathcal U} \newcommand{\pow}{\mathcal P} \newcommand{\inv}{^{-1}} \newcommand{\st}{:} \renewcommand{\iff}{\leftrightarrow} \newcommand{\Iff}{\Leftrightarrow} \newcommand{\imp}{\rightarrow} \newcommand{\Imp}{\Rightarrow} \newcommand{\isom}{\cong} \renewcommand{\bar}{\overline} \newcommand{\card}[1]{\left| #1 \right|} \newcommand{\twoline}[two]{\begin{pmatrix}#1 \\ #2 \terminate{pmatrix}} \newcommand{\vtx}[2]{node[fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2]{}} \newcommand{\va}[1]{\vtx{in a higher place}{#one}} \newcommand{\vb}[1]{\vtx{below}{#ane}} \newcommand{\vr}[1]{\vtx{right}{#1}} \newcommand{\vl}[1]{\vtx{left}{#1}} \renewcommand{\v}{\vtx{above}{}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Investigate!

Consider the graph drawn below.

1. Notice a subgraph with the smallest number of edges that is notwithstanding continued and contains all the vertices.

2. Find a subgraph with the largest number of edges that doesn't comprise any cycles.

3. What practice you notice near the number of edges in your examples above? Is this a coincidence?

One very useful and common arroyo to studying graph theory is to restrict your focus to graphs of a particular kind. For example, you could try to really understand just complete graphs or merely bipartite graphs, instead of trying to understand all graphs in full general. That is what we are going to exercise now, looking at copse. Hopefully past the stop of this department we will have a better agreement of this class of graph, and as well understand why it is of import enough to warrant its own department.

Definition of a Tree.

A tree is a connected graph containing no cycles.⁴

Sometimes this is stated as "a tree is an acyclic continued graph;" "acyclic" is simply a fancy word for "containing no cycles."

A forest is a graph containing no cycles. Notation that this means that a connected woods is a tree.

Does the definition above concord with your intuition for what graphs we should phone call trees? Try thinking of examples of copse and make sure they satisfy the definition. I affair to keep in mind is that while the copse nosotros study in graph theory are related to trees you might run across in other subjects, the correspondence is not verbal. For case, in anthropology, you might written report family trees, like the 1 below,

And then far so good, just while your grandparents are (probably) not claret-relatives, if nosotros go back far enough, it is probable that they did take some common ancestor. If you trace the tree back from you to that common ancestor, then down through your other grandparent, you would have a cycle, and thus the graph would not exist a tree.

Yous might besides have seen something called a decision tree (such as the algorithm for deciding whether a serial converges or diverges). Sometimes these likewise incorporate cycles, equally the decision for one node might lead you back to a previous footstep.

Both the examples of trees in a higher place also have another characteristic worth mentioning: there is a clear lodge to the vertices in the tree. In general, there is no reason for a tree to have this added structure, although we can impose such a structure by considering rooted trees, where nosotros simply designate one vertex equally the root. We will consider such trees in more detail later on in this department.

Subsection Backdrop of Trees

We wish to really empathize copse. This means we should detect properties of trees; what makes them special and what is special about them.

A tree is a connected graph with no cycles. Is in that location anything else we tin can say? Information technology would be nice to have other equivalent conditions for a graph to be a tree. That is, we would like to know whether there are whatsoever graph theoretic properties that all trees have, and perhaps fifty-fifty that only trees take.

To get a feel for the sorts of things nosotros can say, we volition consider three propositions near trees. These will as well illustrate of import proof techniques that employ to graphs in general, and happen to exist a picayune easier for trees.

Our first proffer gives an alternate definition for a tree. That is, it gives necessary and sufficient weather condition for a graph to exist a tree.

Proposition 4.2.1 .

A graph \(T\) is a tree if and just if between every pair of singled-out vertices of \(T\) there is a unique path.

Proof.

This is an "if and simply if" statement, so we must prove two implications. We start by proving that if \(T\) is a tree, then between every pair of distinct vertices in that location is a unique path.

Assume \(T\) is a tree, and let \(u\) and \(v\) be singled-out vertices (if \(T\) only has one vertex, then the conclusion is satisfied automatically). We must show two things to show that in that location is a unique path between \(u\) and \(five\text{:}\) that in that location is a path, and that in that location is not more than one path. The first of these is automatic, since \(T\) is a tree, information technology is connected, so at that place is a path betwixt any pair of vertices.

To prove the path is unique, we suppose in that location are two paths between \(u\) and \(v\text{,}\) and get a contradiction. The two paths might beginning out the same, but since they are different, there is some first vertex \(u'\) afterwards which the two paths diverge. However, since the two paths both terminate and \(v\text{,}\) there is some offset vertex after \(u'\) that they have in mutual, call it \(v'\text{.}\) At present consider the ii paths from \(u'\) to \(v'\text{.}\) Taken together, these grade a bicycle, which contradicts our supposition that \(T\) is a tree.

Now nosotros consider the converse: if between every pair of distinct vertices of \(T\) there is a unique path, then \(T\) is a tree. So assume the hypothesis: between every pair of singled-out vertices of \(T\) there is a unique path. To evidence that \(T\) is a tree, we must show it is connected and contains no cycles.

The first one-half of this is easy: \(T\) is connected, because in that location is a path between every pair of vertices. To prove that \(T\) has no cycles, we assume it does, for the sake of contradiction. Let \(u\) and \(five\) be 2 distinct vertices in a cycle of \(T\text{.}\) Since we can get from \(u\) to \(five\) by going clockwise or counterclockwise around the cycle, there are two paths from \(u\) and \(v\text{,}\) contradicting our supposition.

We take established both directions and then we have completed the proof.

Read the proof above very carefully. Notice that both directions had two parts: the existence of paths, and the uniqueness of paths (which related to the fact that there were no cycles). In this instance, these two parts were really separate. In fact, if we only considered graphs with no cycles (a forest), then nosotros could nonetheless do the parts of the proof that explore the uniqueness of paths between vertices, even if there might not exist paths between vertices.

This observation allows united states of america to land the following corollary:^v

A corollary is some other sort of provable argument, like a proposition or theorem, but one that follows direction from another already established statement, or its proof.

Corollary 4.2.2 .

A graph \(F\) is a forest if and only if between whatever pair of vertices in \(F\) there is at near 1 path.

Nosotros do not requite a proof of the corollary (it is, after all, supposed to follow directly from the suggestion) but for do, yous are asked to requite a careful proof in the exercises. When you do then, try to use proof by contrapositive instead of proof by contradiction.

Our second proposition tells the states that all trees accept leaves: vertices of degree ane.

Proffer iv.two.3 .

Any tree with at least two vertices has at least two vertices of degree one.

Proof.

We requite a proof past contradiction. Allow \(T\) be a tree with at least two vertices, and suppose, contrary to stipulation, that there are not two vertices of degree ane.

Allow \(P\) exist a path in \(T\) of longest possible length. Let \(u\) and \(5\) be the endpoints of the path. Since \(T\) does not accept 2 vertices of degree i, at least one of these must take degree two or higher. Say that it is \(u\text{.}\) We know that \(u\) is adjacent to a vertex in the path \(P\text{,}\) simply at present it must too be side by side to another vertex, call it \(u'\text{.}\)

Where is \(u'\text{?}\) It cannot be a vertex of \(P\text{,}\) because if information technology was, there would be ii distinct paths from \(u\) to \(u'\text{:}\) the edge between them, and the beginning function of \(P\) (up to \(u'\)). But \(u'\) also cannot be outside of \(P\text{,}\) for if it was, in that location would be a path from \(u'\) to \(v\) that was longer than \(P\text{,}\) which has longest possible length.

This contradiction proves that in that location must be at least 2 vertices of degree one. In fact, we can say a footling more than: \(u\) and \(five\) must both accept degree 1.

The proffer is quite useful when proving statements nearly trees, because nosotros often prove statements nigh trees by induction. To do and then, we need to reduce a given tree to a smaller tree (so nosotros can employ the anterior hypothesis). Getting rid of a vertex of degree i is an obvious choice, and at present we know there is ever one to get rid of.

To illustrate how consecration is used on trees, nosotros will consider the relationship between the number of vertices and number of edges in trees. Is there a tree with exactly 7 vertices and 7 edges? Try to describe ane. Could a tree with 7 vertices have simply 5 edges? There is a skillful reason that these seem incommunicable to draw.

Suggestion 4.2.4 .

Let \(T\) exist a tree with \(v\) vertices and \(e\) edges. And so \(e = v-1\text{.}\)

Proof.

We will give a proof by consecration on the number of vertices in the tree. That is, we volition prove that every tree with \(v\) vertices has exactly \(v-one\) edges, and and so apply induction to testify this is true for all \(v \ge 1\text{.}\)

For the base of operations case, consider all trees with \(v = i\) vertices. There is only one such tree: the graph with a single isolated vertex. This graph has \(e = 0\) edges, so we meet that \(e = v-one\) as needed.

Now for the anterior case, fix \(k \ge 1\) and presume that all trees with \(v=chiliad\) vertices have exactly \(e=k-1\) edges. Now consider an arbitrary tree \(T\) with \(five = m+1\) vertices. By Proposition four.2.3, \(T\) has a vertex \(v_0\) of caste ane. Let \(T'\) be the tree resulting from removing \(v_0\) from \(T\) (together with its incident edge). Since nosotros removed a leaf, \(T'\) is all the same a tree (the unique paths between pairs of vertices in \(T'\) are the same as the unique paths betwixt them in \(T\)).

At present \(T'\) has \(yard\) vertices, so by the inductive hypothesis, has \(k-1\) edges. What can we say most \(T\text{?}\) Well, it has 1 more border than \(T'\text{,}\) so it has \(g\) edges. But this is exactly what we wanted: \(v=k+i\text{,}\) \(east=thousand\) and then indeed \(e = v-i\text{.}\) This completes the inductive case, and the proof.

There is a very important characteristic of this induction proof that is worth noting. Induction makes sense for proofs about graphs because nosotros tin can remember of graphs equally growing into larger graphs. Withal, this does NOT piece of work. It would not be correct to kickoff with a tree with \(g\) vertices, and then add a new vertex and edge to get a tree with \(k+1\) vertices, and notation that the number of edges also grew by 1. Why is this bad? Because how do you know that every tree with \(k+one\) vertices is the outcome of calculation a vertex to your arbitrary starting tree? You don't!

The point is that whenever you lot give an induction proof that a statement about graphs that holds for all graphs with \(5\) vertices, yous must start with an arbitrary graph with \(5+1\) vertices, then reduce that graph to a graph with \(v\) vertices, to which you can apply your inductive hypothesis.

Subsection Rooted Copse

Then far, we accept idea of copse only every bit a particular kind of graph. Yet, it is often useful to add boosted structure to trees to help solve problems. Data is often structured like a tree. This book, for example, has a tree structure: draw a vertex for the book itself. And then draw vertices for each chapter, connected to the volume vertex. Nether each chapter, draw a vertex for each department, connecting it to the chapter information technology belongs to. The graph volition not have any cycles; it will exist a tree. But a tree with clear hierarchy which is not present if we don't identify the book vertex equally the "top".

As before long every bit one vertex of a tree is designated as the root, then every other vertex on the tree can be characterized by its position relative to the root. This works because there is a unique path between whatsoever two vertices in a tree. So from whatever vertex, we can travel dorsum to the root in exactly one way. This also allows us to describe how distinct vertices in a rooted tree are related.

If two vertices are next, then we say ane of them is the parent of the other, which is called the kid of the parent. Of the two, the parent is the vertex that is closer to the root. Thus the root of a tree is a parent, only is not the kid of any vertex (and is unique in this respect: all non-root vertices have exactly one parent).

Not surprisingly, the child of a child of a vertex is called the grandchild of the vertex (and it is the grandparent). More in general, we say that a vertex \(5\) is a descendent of a vertex \(u\) provided \(u\) is a vertex on the path from \(five\) to the root. Then we would call \(u\) an ancestor of \(v\text{.}\)

For near trees (in fact, all except paths with one end the root), there volition be pairs of vertices neither of which is a descendant of the other. Nosotros might telephone call these cousins or siblings. In fact, vertices \(u\) and \(v\) are called siblings provided they have the aforementioned parent. Note that siblings are never adjacent (do you lot see why?).

Instance 4.2.five .

Consider the tree below.

If nosotros designate vertex \(f\) as the root, then \(due east\text{,}\) \(h\text{,}\) and \(i\) are the children of \(f\text{,}\) and are siblings of each other. Among the other things we cay say are that \(a\) is a child of \(c\text{,}\) and a descendant of \(f\text{.}\) The vertex \(one thousand\) is a descendant of \(f\text{,}\) in fact, is a grandchild of \(f\text{.}\) Vertices \(g\) and \(d\) are siblings, since they accept the common parent \(e\text{.}\)

Notice how this changes if we selection a different vertex for the root. If \(a\) is the root, and so its lone child is \(c\text{,}\) which also has only one kid, namely \(e\text{.}\) We would then have \(f\) the kid of \(e\) (instead of the other way around), and \(f\) is the descendant of \(a\text{,}\) instead of the ancestor. \(f\) and \(g\) are at present siblings.

All of this flowery linguistic communication helps us describe how to navigate through a tree. Traversing a tree, visiting each vertex in some order, is a key step in many algorithms. Fifty-fifty if the tree is non rooted, we can ever form a rooted tree by picking any vertex every bit the root. Here is an example of why doing and then can be helpful.

Case 4.two.half dozen .

Explain why every tree is a bipartite graph.

Solution

To show that a graph is bipartite, we must divide the vertices into ii sets \(A\) and \(B\) so that no ii vertices in the same gear up are adjacent. Hither is an algorithm that does just this.

Designate any vertex as the root. Put this vertex in set \(A\text{.}\) Now put all of the children of the root in set \(B\text{.}\) None of these children are next (they are siblings), and so we are skilful so far. Now put into \(A\) every child of every vertex in \(B\) (i.e., every grandchild of the root). Go on going until all vertices take been assigned one of the sets, alternating between \(A\) and \(B\) every "generation." That is, a vertex is in set \(B\) if and just if it is the child of a vertex in set \(A\text{.}\)

The cardinal to how we partitioned the tree in the example was to know which vertex to assign to a prepare next. We chose to visit all vertices in the same generation earlier whatever vertices of the next generation. This is usually called a latitude first search (nosotros say "search" considering you often traverse a tree looking for vertices with certain properties).

In contrast, we could also accept partitioned the tree in a different order. Outset with the root, put information technology in \(A\text{.}\) And so await for one child of the root to put in \(B\text{.}\) And so find a child of that vertex, into \(A\text{,}\) and then find its child, into \(B\text{,}\) and and then on. When you get to a vertex with no children, retreat to its parent and see if the parent has any other children. So we travel equally far from the root equally fast as possible, then backtrack until we can move frontward again. This is chosen depth first search.

These algorithmic explanations can serve as a proof that every tree is bipartite, although care needs to be spent to prove that the algorithms are right. Some other approach to prove that all trees are bipartite, using induction, is requested in the exercises.

Subsection Spanning Trees

One of the advantages of trees is that they give us a few simple ways to travel through the vertices. If a connected graph is not a tree, then nosotros can still employ these traversal algorithms if we identify a subgraph that is a tree.

First nosotros should consider if this even makes sense. Given any connected graph \(Thou\text{,}\) will in that location always be a subgraph that is a tree? Well, that is actually too easy: y'all could just take a single vertex of \(G\text{.}\) If we desire to employ this subgraph to tell united states of america how to visit all vertices, and so nosotros want our subgraph to include all of the vertices. We phone call such a tree a spanning tree. It turns out that every continued graph has one (and ordinarily many).

Spanning tree.

Given a connected graph \(G\text{,}\) a spanning tree of \(Thou\) is a subgraph of \(M\) which is a tree and includes all the vertices of \(G\text{.}\)

Every continued graph has a spanning tree.

How do we know? We tin requite an algorithm for finding a spanning tree! Start with a connected graph \(G\text{.}\) If there is no bicycle, then \(G\) is already a tree and nosotros are done. If there is a cycle, let \(e\) exist any border in that cycle and consider the new graph \(G_1 = G - e\) (i.eastward., the graph you become past deleting \(east\)). This tree is still connected since \(e\) belonged to a bike, there were at to the lowest degree two paths between its incident vertices. Now repeat: if \(G_1\) has no cycles, we are done, otherwise ascertain \(G_2\) to be \(G_1 - e_1\text{,}\) where \(e_1\) is an edge in a wheel in \(G_1\text{.}\) Go along going. This process must eventually end, since there are but a finite number of edges to remove. The result will exist a tree, and since we never removed whatsoever vertex, a spanning tree.

This is past no means the only algorithm for finding a spanning tree. Y'all could accept started with the empty graph and added edges that belong to \(G\) every bit long as adding them would not create a cycle. You have some choices every bit to which edges you add first: you could ever add an edge adjacent to edges you accept already added (subsequently the first one, of form), or add them using some other order. Which spanning tree you finish up with depends on these choices.

Example 4.ii.7 .

Find two different spanning trees of the graph,

Although we volition not consider this in detail, these algorithms are normally applied to weighted graphs. Here every edge has some weight or cost assigned to it. The goal is to find a spanning tree that has the smallest possible combined weight. Such a tree is called a minimum spanning tree. Finding the minimum spanning tree uses basically the aforementioned algorithms every bit nosotros described in a higher place, just when picking an border to add together, yous e'er pick the smallest (or when removing an edge, you always remove the largest).⁶

If y'all add the smallest edge adjacent to edges you have already added, you are doing Prim's algorithm. If you add the smallest edge in the unabridged graph, you are following Kruskal's algorithm.

Exercises Exercises

1.

Which of the following graphs are copse?

1. \(G = (Five, E)\) with \(Five = \{a, b, c, d, east\}\) and \(E = \{\{a, b\}, \{a,e\}, \{b, c\}, \{c,d\}, \{d,e\} \}\)

2. \(One thousand = (5, E)\) with \(V = \{a, b, c, d, e\}\) and \(Eastward = \{\{a, b\}, \{b, c\}, \{c,d\}, \{d,e\}\}\)

3. \(G = (5, Eastward)\) with \(V = \{a, b, c, d, e\}\) and \(Due east = \{\{a, b\}, \{a, c\}, \{a,d\}, \{a,e\}\}\)

4. \(G = (V, E)\) with \(V = \{a, b, c, d, e\}\) and \(E = \{\{a, b\}, \{a, c\}, \{d,e\}\}\)

Solution

1. This is not a tree since it contains a cycle. Notation also that in that location are too many edges to be a tree, since we know that all trees with \(v\) vertices have \(v-one\) edges.

2. This is a tree since information technology is connected and contains no cycles (which you can see by drawing the graph). All paths are copse.

3. This is a tree since it is continued and contains no cycles (draw the graph). All stars are trees.

4. This is a non a tree since it is not connected. Note that there are non enough edges to be a tree.

2.

For each degree sequence below, decide whether information technology must always, must never, or could possibly be a degree sequence for a tree. Call up, a degree sequence lists out the degrees (number of edges incident to the vertex) of all the vertices in a graph in non-increasing order.

1. \(\displaystyle (4,i,i,i,1)\)

2. \(\displaystyle (3,3,2,1,i)\)

3. \(\displaystyle (ii,2,2,1,1)\)

4. \(\displaystyle (four, 4, three, 3, 3, 2, ii, 1, i, 1, 1, 1, 1, 1)\)

Solution

1. This must exist the degree sequence for a tree. This is because the vertex of caste 4 must exist side by side to the iv vertices of degree 1 (there are no other vertices for it to be adjacent to), and thus we get a star.

2. This cannot exist a tree. Each degree 3 vertex is adjacent to all but one of the vertices in the graph. Thus each must exist next to one of the caste 1 vertices (and not the other). That means both degree 3 vertices are adjacent to the degree 2 vertex, and to each other, so that means there is a cycle.

   Alternatively, count how many edges there are!

3. This might or might not be a tree. The length four path has this degree sequence (this is a tree), only so does the wedlock of a 3-cycle and a length 1 path (which is not continued, so not a tree).

4. This cannot exist a tree. The sum of the degrees is 28, so there are 14 edges. Simply there are fourteen vertices as well, so we don't have \(five = e+1\text{,}\) pregnant this cannot be a tree.

3.

For each degree sequence beneath, determine whether it must always, must never, or could possibly be a degree sequence for a tree. Justify your answers.

1. \(\displaystyle (iii, 3, 2, 2, 2)\)

2. \(\displaystyle (iii, ii, 2, one, 1, 1)\)

3. \(\displaystyle (3, 3, three, ane, 1, 1)\)

4. \(\displaystyle (4, 4, 1, ane, 1, 1, 1, 1)\)

Hint

Careful: the graphs might not be connected.

4.

Suppose you take a graph with \(v\) vertices and \(e\) edges that satisfies \(v = eastward+i\text{.}\) Must the graph be a tree? Prove your reply.

five.

Prove that whatever graph (not necessarily a tree) with \(v\) vertices and \(due east\) edges that satisfies \(v \gt e+1\) will Not exist connected.

Hint

Attempt a proof past contradiction and consider a spanning tree of the graph.

6.

If a graph \(G\) with \(v\) vertices and \(e\) edges is continued and has \(v \lt e+i\text{,}\) must it incorporate a cycle? Bear witness your answer.

Solution

Yep. We will prove the contrapositive. Assume \(G\) does not contain a bike. And then \(G\) is a tree, so would accept \(v = eastward+1\text{,}\) reverse to stipulation.

7.

We define a woods to be a graph with no cycles.

1. Explicate why this is a good name. That is, explain why a woods is a union of trees.

2. Suppose \(F\) is a wood consisting of \(thousand\) trees and \(v\) vertices. How many edges does \(F\) have? Explain.

3. Evidence that any graph \(K\) with \(v\) vertices and \(e\) edges that satisfies \(v \lt e+i\) must incorporate a wheel (i.e., non be a forest).

Hint

For part (b), trying some simple examples should give y'all the formula. Then you only need to prove it is correct.

viii.

Requite a conscientious proof of Corollary 4.ii.2: A graph is a forest if and only if there is at almost one path between any pair of vertices. Employ proof past contrapositive (and non a proof by contradiction) for both directions.

Hint

Examining the proof of Proposition 4.2.1 gives you most of what you need, simply brand sure to simply give the relevant parts, and take care to not employ proof by contradiction.

9.

Give a careful proof by induction on the number of vertices, that every tree is bipartite.

Hint

Y'all will need to remove a vertex of degree one, apply the inductive hypothesis to the result, and and so say which set the degree 1 vertex to.

10.

Consider the tree drawn below.

1. Suppose we designate vertex \(due east\) as the root. List the children, parents and siblings of each vertex. Does whatever vertex other than \(e\) have grandchildren?

2. Suppose \(due east\) is not chosen as the root. Does our choice of root vertex change the number of children \(e\) has? The number of grandchildren? How many are there of each?

3. In fact, pick any vertex in the tree and suppose it is non the root. Explicate why the number of children of that vertex does not depend on which other vertex is the root.

4. Does the previous part work for other copse? Give an example of a unlike tree for which it holds. So either prove that it always holds or give an case of a tree for which it doesn't.

Hint

If \(due east\) is the root, then \(b\) volition have iii children (\(a\text{,}\) \(c\text{,}\) and \(d\)), all of which will exist siblings, and have \(b\) as their parent. \(a\) will not have any children.

In general, how can you decide the number of children a vertex volition accept, if it is non a root?

11.

Let \(T\) be a rooted tree that contains vertices \(u\text{,}\) \(v\text{,}\) and \(west\) (amid possibly others). Bear witness that if \(westward\) is a descendant of both \(u\) and \(v\text{,}\) so \(u\) is a descendant of \(v\) or \(v\) is a descendant of \(u\text{.}\)

12.

Unless it is already a tree, a given graph \(Yard\) volition have multiple spanning copse. How similar or dissimilar must these be?

1. Must all spanning trees of a given graph be isomorphic to each other? Explain why or give a counterexample.

2. Must all spanning copse of a given graph have the aforementioned number of edges? Explain why or requite a counterexample.

3. Must all spanning trees of a graph accept the same number of leaves (vertices of caste 1)? Explain why or give a counterexample.

Solution

1. No, although there are graphs for which this is true. For case, \(K_4\) has a spanning tree that is a path (of three edges) and also a spanning tree that is a star (with center vertex of degree 3).

2. Yes. For a fixed graph, we have a fixed number \(v\) of vertices. Whatsoever spanning tree of the graph will also accept \(v\) vertices, and since information technology is a tree, must have \(5-one\) edges.

3. No, although there are graph for which this is true (note that if all spanning trees are isomorphic, then all spanning trees will have the same number of leaves). Again, \(K_4\) is a counterexample. Ane spanning tree is a path, with only two leaves, another spanning tree is a star with 3 leaves.

13.

Find all spanning trees of the graph below. How many different spanning trees are at that place? How many different spanning trees are there upwardly to isomorphism (that is, if y'all grouped all the spanning trees past which are isomorphic, how many groups would you take)?

14.

Give an case of a graph that has exactly 7 dissimilar spanning trees. Note, it is acceptable for some or all of these spanning copse to be isomorphic.

Hint

There is an example with 7 edges.

fifteen.

Prove that every connected graph which is not itself a tree must have at concluding iii unlike (although possibly isomorphic) spanning copse.

Hint

The previous practice will be helpful.

xvi.

Consider edges that must be in every spanning tree of a graph. Must every graph have such an edge? Give an example of a graph that has exactly one such edge.

Hint

Note that such an edge, if removed, would disconnect the graph. We telephone call graphs that accept an border similar this 1-connected.

solanoskiatio.blogspot.com

Source: http://discrete.openmathbooks.org/dmoi3/sec_trees.html

Share this post