0
Prove that a graph G is connected and only if it has a spanning tree?
Wiki User
∙ 14y ago
Proving this is simple. First, you prove that G has a spanning tree, it is connected, which is pretty obvious - a spanning tree itself is already a connected graph on the vertex set V(G), thus G which contains it as a spanning sub graph is obviously also connected.
Second, you prove that if G is connected, it has a spanning tree. If G is a tree itself, then it must "contain" a spanning tree. If G is connected and not a tree, then it must have at least one cycle. I don't know if you know this or not, but there is a theorem stating that an edge is a cut-edge if and only if it is on no cycle (a cut-edge is an edge such that if you take it out, the graph becomes disconnected). Thus, you can just keep taking out edges from cycles in G until all that is left are cut-gees. Since you did not take out any cut-edges, the graph is still connected; since all that is left are cut-edges, there are no cycles. A connected graph with no cycles is a tree. Thus, G contains a spanning tree.
Therefore, a graph G is connected if and only if it has a spanning tree!
Clark Schimmel
Add your answer:
Earn +20 pts
What is directly and invertly related on a graph?
The x value and the y value are directly and invertly related on a graph. This only occurs in a specific type of graph called a proportional graph.
Why do come function graphs have just points and some have a line connected?
Most functions are continuous (connected line), and not just two points... 2 points are simply just coordinates on a graph, and would be very hard (perhaps impossible) to make into a function (unless you have a restricted domain) I may be wrong, but I don't think I am A function has to be a graph that can be expressed through an equation, and only has a max of one y coordinate for each x coordinate, although it may have zero
What do the numbers below the graph show?
It's difficult to make out enough detail to formulate an answer. Not only can't I see the numbers below the graph, I can't even see the graph.
What is a graph made of only distinct points?
Scatter plot
How many edges must a simple graph with n vertices have in order to guarantee that it is connected?
The non-connected graph on n vertices with the most edges is a complete graph on n-1 vertices and one isolated vertex. So you must have one more than (n-1)n/2 edges to guarantee connectedness. It is easy to see that the extremal graph must be the union of two disjoint cliques (complete graphs). (Proof:In a non-connected graph with parts that are not cliques, add edges to each part until all are cliques. You will not have changed the number of parts. If there are more than two disjoint cliques, you can join cliques [add all edges between them] until there are only two.) It is straightforward to create a quadratic expression for the number of edges in two disjoint cliques (say k vertices in one clique, n-k in the other). Basic algebra will show that the maximum occurs when k=1 or n-1. (We're not allowing values outside that range.)
Prove that a graph G is connected if and only if it has a spanning tree?
Proving this is simple. First, you prove that G has a spanning tree, it is connected, which is pretty obvious - a spanning tree itself is already a connected graph on the vertex set V(G), thus G which contains it as a spanning sub graph is obviously also connected. Second, you prove that if G is connected, it has a spanning tree. If G is a tree itself, then it must "contain" a spanning tree. If G is connected and not a tree, then it must have at least one cycle. I don't know if you know this or not, but there is a theorem stating that an edge is a cut-edge if and only if it is on no cycle (a cut-edge is an edge such that if you take it out, the graph becomes disconnected). Thus, you can just keep taking out edges from cycles in G until all that is left are cut-gees. Since you did not take out any cut-edges, the graph is still connected; since all that is left are cut-edges, there are no cycles. A connected graph with no cycles is a tree. Thus, G contains a spanning tree. Therefore, a graph G is connected if and only if it has a spanning tree!
What is Difference between tree and spanning tree?
A tree is a connected graph in which only 1 path exist between any two vertices of the graph i.e. if the graph has no cycles. A spanning tree of a connected graph G is a tree which includes all the vertices of the graph G.There can be more than one spanning tree for a connected graph G.
Prove that every tree with two or more vertices is bichromatic?
Prove that the maximum vertex connectivity one can achieve with a graph G on n. 01. Define a bipartite graph. Prove that a graph is bipartite if and only if it contains no circuit of odd lengths. Define a cut-vertex. Prove that every connected graph with three or more vertices has at least two vertices that are not cut vertices. Prove that a connected planar graph with n vertices and e edges has e - n + 2 regions. 02. 03. 04. Define Euler graph. Prove that a connected graph G is an Euler graph if and only if all vertices of G are of even degree. Prove that every tree with two or more vertices is 2-chromatic. 05. 06. 07. Draw the two Kuratowski's graphs and state the properties common to these graphs. Define a Tree and prove that there is a unique path between every pair of vertices in a tree. If B is a circuit matrix of a connected graph G with e edge arid n vertices, prove that rank of B=e-n+1. 08. 09.
Why you use DFS and BFS in graphs?
DFS and BFS are both searching algorithms. DFS, or depth first search, is a simple to implement algorithm, especially when written recursively. BFS, or breadth first search, is only slightly more complicated. Both search methods can be used to obtain a spanning tree of the graph, though if I recall correctly, BFS can also be used in a weighted graph to generate a minimum cost spanning tree.
How do you approximate the traveling salesman problem?
Given an un-directed fully connected graph (there is an edge between every two vertices) with a weight function that has the triangle inequality. I.e., if (u,v), (v,w), (u,w) in E then w(u,v) + w(v,w) >= w(u,w). Do:find a minimum spanning treesplit each edge in the tree into two edges. Since all the degrees in the new graph are even, there is an Euler cycle in the graph. Find it.Whenever you can, cut corners. I.e., if the Euler path goes: v --> u --> v --> w, change it to go: v --> u --> w. From the assumptions on the graph we can only gain from this and we are guaranteed that there an edge u --> w.Ratio from the optimum:Note that the optimum (opt) path costs at most the value of the MST (just take one edge off the opt and you get a spanning tree). Since our path is at most twice the cost of the spanning tree we have a ratio of x2.
Why prims algorithm is better than kruskals algorithm?
"What are difference between Prim's algorithm and Kruskal's algorithm for finding the minimum spanning tree of a graph?" Prim's method starts with one vertex of a graph as your tree, and adds the smallest edge that grows your tree by one more vertex. Kruskal starts with all of the vertices of a graph as a forest, and adds the smallest edge that joins two trees in the forest. Prim's method is better when * You can only concentrate on one tree at a time * You can concentrate on only a few edges at a time Kruskal's method is better when * You can look at all of the edges at once * You can hold all of the vertices at once * You can hold a forest, not just one tree Basically, Kruskal's method is more time-saving (you can order the edges by weight and burn through them fast), while Prim's method is more space-saving (you only hold one tree, and only look at edges that connect to vertices in your tree).
Show that the star graph is the only bipartiate graph which is a tree?
A star graph, call it S_k is a complete bipartite graph with one vertex in the center and k vertices around the leaves. To be a tree a graph on n vertices must be connected and have n-1 edges. We could also say it is connected and has no cycles. Now a star graph, say S_4 has 3 edges and 4 vertices and is clearly connected. It is a tree. This would be true for any S_k since they all have k vertices and k-1 edges. And Now think of K_1,k as a complete bipartite graph. We have one internal vertex and k vertices around the leaves. This gives us k+1 vertices and k edges total so it is a tree. So one way is clear. Now we would need to show that any bipartite graph other than S_1,k cannot be a tree. If we look at K_2,k which is a bipartite graph with 2 vertices on one side and k on the other,can this be a tree?
How does an only child prove there are no other siblings?
Prove to whom? You can't "prove" a negative.
Can a bar graph be used to display only numerical data?
histogram; bar graph
What is directly and invertly related on a graph?
The x value and the y value are directly and invertly related on a graph. This only occurs in a specific type of graph called a proportional graph.
What might a graph show that a data table does not?
The graph could go on forever while a data table only shows a part of the graph.
Why is it risky to draw a graph after plotting only two points when using the equation yx?
With only two points you don't know the direction of the graph. Drawing a graph using only two points can result in the diagram being wrong.
