0
Still curious? Ask our experts.
Chat with our AI personalities
Rafa
Professor
MaxineAdd your answer:
Earn +20 pts
Prove that a graph G is connected 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!
When the value of the slope gets smaller the graph gets?
As the slope get closer to zero, the graph becomes close to horizontal.
What is a rooted tree in graph theory?
A tree in which one vertex called the root, is distinguished from all the others is called a rooted tree.
When the value of a slope gets bigger the graph of a line gets?
As the slope gets bigger the graph becomes closer to vertical - from bottom left to top right.
What are the names of the on a graph?
bar graph, double bar graph, line graph, and picto graph
