0
$\begingroup$

Exactly the last part of this which I made it bold and says it is obvious is not obvious for me, I don't want to write it like that to my report, 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

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.

As for (iv), we do not even need the inductive hypothesis for G−v. Since G is connected, any two vertices x, y ∈ V (G) can be connected by a path, and if {x, y} ∉ E(G) then the edge {x,y} together with the just-mentioned path creates a cycle. This proves the implication (i)⇒ (iv).

Now we prove that each of the conditions (ii)–(v) implies (i). In (ii) and (iii) we already assume connectedness. Moreover, a graph satisfying (ii) or (iii) cannot contain a cycle. For (ii), this is because two vertices in a cycle can be connected by two distinct paths, and for (iii), the reason is that by omitting an edge in a cycle we obtain a connected graph. Thus we have already proved the equivalence of (i)–(iii).

In order to verify the implication (iv)⇒(i), it suffices to check that G is connected. For this, we can use the argument by which we have proved (i)⇒(iv) turned upside down. If x, y ∈ V (G) are two vertices, either they are connected by an edge, or the graph G+{x, y} contains a cycle, and removing the edge {x, y} from this cycle gives a path from x to y in G.

Finally the implication (v)⇒(i) is again proved by induction on the number of vertices. Let us consider a connected graph G satisfying |V | = |E| + 1 ≥ 2. The sum of the degrees of all vertices is thus 2|V | − 2 . This means that not all vertices can have degree 2 or larger, and since all the degrees are at least 1 (by connectedness!), there exists a vertex v of degree exactly 1, i.e. an end-vertex of the graph G. The graph G′ = G − v is again connected and it satisfies |V (G′)| = |E(G′)|+ 1. Hence it is a tree by the inductive hypothesis, and thus G is a tree as well.

| cite | improve this question | | | | |
$\endgroup$
  • $\begingroup$ There are $6$ possible implications here. Surely some of them are clear to you. Which ones can you see, and which do you not understand? $\endgroup$ – saulspatz Jul 23 '19 at 16:10
  • $\begingroup$ where it is written In this situation, the validity of (ii), (iii), and (v) for G can be considered obvious $\endgroup$ – Sina M Jul 23 '19 at 16:12
  • $\begingroup$ Yes, you said that already. I mean there are $6$ possible implications of the form (ii)$\implies$(iii) or (v)$\implies$(ii) etc. Which can you see and which can you not see? $\endgroup$ – saulspatz Jul 23 '19 at 16:14
  • $\begingroup$ @saulspatz the thing is I want to write this on a report, I don't know just saying this is obvious is enough... I want it to explain everything, I don't know it is enough this way. $\endgroup$ – Sina M Jul 23 '19 at 16:37
  • $\begingroup$ @saulspatz can I have all six? $\endgroup$ – Sina M Jul 23 '19 at 16:58
0
$\begingroup$

I think that if you review the definition of a tree, the statements you're asking about will reflect basic properties of a tree.

From Wikipedia: " ... a tree is an undirected graph in which any two vertices are connected by exactly one path, or equivalently a connected acyclic undirected graph."

So (ii) follows directly from the definition. Statement (iii) does as well, because if you take away the only path between two vertices, there is no other path connecting them, and the tree will be disconnected. Statement (v) you can probably convince yourself of as well.

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ Thank you, but the thing is I wanted to know if in a report I would write this is obvious I wouldn't be rejected or should I explain instead of writing this is obvious $\endgroup$ – Sina M Jul 23 '19 at 16:50
  • $\begingroup$ If saying "this is obvious" makes you uncomfortable, then you can quote the definition of a tree (from whatever source is appropriate), and then say that the statements follow from the definition. (Statement (i) establishes that we're talking about a tree.) $\endgroup$ – John Jul 23 '19 at 19:50
  • $\begingroup$ That's what I wanted, a trick :) thank you $\endgroup$ – Sina M Jul 23 '19 at 20:02
  • $\begingroup$ can you please kindly show me a academic cite able definition? $\endgroup$ – Sina M Jul 24 '19 at 21:24
  • $\begingroup$ I'm well out of academia now; I wouldn't even know where to look at this point. Best to you. $\endgroup$ – John Jul 25 '19 at 2:42

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.