0
$\begingroup$

Exactly the last part of this which I made it bold and says it is obvious is not obvious for me, can you explain it to me?

Theorem: The following conditions are all equivalent for a graph G = (V, E): [1]

(i) G is a tree. (ii) (Path uniqueness) For every two vertices x, y ∈ V , there exists exactly one path from x to y. (iii) (Minimal connected graph) The graph G is connected, and deleting any of its edges gives rise to a disconnected graph. (iv) (Maximal graph without cycles) The graph G contains no cycle, and any graph arising from G by adding an edge already contains a cycle.

(v) (Euler’s formula) G is connected and |V | = |E| + 1

Lemma (Tree-growing lemma). The following two statements are equivalent for a graph G and its end-vertex v: (i) G is a tree (ii) G − v is a tree.

Proof of Lemma: First we prove the implication (i)⇒ (ii). The graph G is a tree, and we want to prove that G − v is a tree as well. Consider two vertices x, y of G−v. Since G is connected, x and y are connected by a path in G. This path cannot contain a vertex of degree 1 (he degree of a vertex of a graph is the number of edges that are incident to the vertex) different from both x and y, and so it doesn’t contain v. Therefore it is completely contained in G − v, and we conclude that G − v is connected. Since G has no cycle, obviously G − v cannot contain a cycle, and thus it is a tree. It remains to prove the implication (ii)⇒ (i). Let G−v be a tree. By adding the end-vertex v back to it, no cycle can be created. We must also check the connectedness of G: any two vertices distinct from v were connected already in G − v, and a path to v from any other vertex x is obtained by considering the (single) neighbor v′of v in G, connecting it to x by a path in G − v, and extending this path by the edge {v′, v}.

This lemma allows us to reduce a given tree to smaller and smaller trees by removing end-vertices successively. Now we are going to apply this device.

Proof of Theorem:

We prove that each of the statements (ii)–(v) is equivalent to (i). This, of course, proves the mutual equivalence of all the statements. The proofs go by induction on the number of vertices of G using the tree-growing lemma As for the induction basis, we note that all the statements are valid for the graph with a single vertex.

First we that (i) implies all of (ii)–(v). To this end, let G be a tree with at least 2 vertices, let v be one of its end-vertices, and let v′ be the single neighbor of v in G. Suppose that the graph G−v already satisfies (ii)–(v); this is our inductive hypothesis.

In this situation, the validity of (ii), (iii), and (v) for G can be considered obvious

$\endgroup$
0
$\begingroup$

The text claims that the validity of these elements is obvious, as they describe some elementary properties of trees. I'll try talking through these properties to explain them, in less formal language.

(ii) For the base case we have a tree of two nodes connected by a single vertex. There exists only a single path between each. If we expand the tree by a single node we also must add one and only one vertex connecting the new node to one of the existing nodes. There still exists only one path from the new node to any of the others.

(iii) Using (ii) tells us that since there exists only one path from any node to any other. Therefore the only path from a node to its parent is through the vertex added with the node, if that vertex is removed then there no longer exists a path from the child to parent making the graph disconnected.

(v) For this I'm assuming the notation of |V| is the degree (number of connected vertices) of V, and |E| is the number of children the node has.

Again we look at the tree growing lemma, a node is added to the tree by adding it and a vertex to its parent node. The number of vertices of a leaf node is 1, for each child we add to the node its degree is also incremented by 1.

As such the degree of any node is the number of children |E| plus 1 (for the parent), except in the case of the root which by definition does not have a parent.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.