a)Let graph $T=(V,E,f)$ where $|V|=n>1$

Prove that those statements are equivalents:

  1. T is a tree;
  2. For each $v$ $\in$ V there's only a path from $u$ to $v$.

b) Let G a connected graph whose vertexes are all even. Prove that for each edge $e \in E(G)$ the graph you obtain deleting that edge keeps being connected.

c) Prove that if a graph has no loops, then it has at least a 1-degree vertex or it is an empty graph.


a) $=>$ for definition of tree, what about $<=$?

b) A graph is connected if for each vertex $v,z \in V$ there is a path from $v$ to $z$. If all the vertexes are even, then each vertex is connected with other 2 ones, then removing 1 edge won't compromise the connectednessof the whole graph.

c) if the graph has no loops it could be an empty graph or a tree. If it's a tree then it has at least 1-degree vertex. (Because every tree has at least a leaf and a leaf is 1-degre vertex)

  • 1
    $\begingroup$ I think your intuition is off for (b). If we take two large complete graphs and join them by a single edge e, then we have a connected graph and every vertex has large degree, but removing e results in a disconnected graph. (I don't think (b) is obvious.) $\endgroup$ – Rebecca J. Stones Jan 23 '14 at 21:50
  • $\begingroup$ It is in my opinion, because it says all vertexes are even, which means that evey vertex is connected with at least 2 other ones. So removing only 1 edge will keep it connected. $\endgroup$ – Angelo Tricarico Jan 23 '14 at 21:53
  • $\begingroup$ @Deleted your proof of (b) is not valid (which proves that it is not obvious at all), Rebecca is right. $\endgroup$ – Denis Jan 25 '14 at 20:40
  • $\begingroup$ @dkuper so the proof stays in the fact that every graph has an even number of odd vertexes? $\endgroup$ – Angelo Tricarico Jan 25 '14 at 21:11
  • $\begingroup$ @Deleted Not exactly: if you 2 odd vertices, then you can do a hamiltonian path. More importantly, if you have no odd vertex, you can do a hamiltonian cycle. $\endgroup$ – Denis Jan 25 '14 at 21:13

For (a), a tree is a connected graph without cycles. The connectedness condition is immediate by assumption in both cases, so we check:

  • If there were two distinct paths connecting two vertices, then there is a cycle, and
  • If there were a cycle, then there are two distinct paths connecting two vertices.

(The task is to identify two paths and a cycle in these cases.)

For (b), suppose the removal of the edge $e$ results in two connected components, $H_1$ and $H_2$ say. What are the degrees of the vertices in $H_1$? Can this satisfy the Handshaking Lemma?

For (c), "loops" here are usually referred to as "cycles". This is also only true for finite graphs (and we'll need that assumption for the proof). If the graph is non-empty, we start from a vertex with an adjacent edge and take a walk:

  • if we encounter the same vertex more than once, then ???
  • otherwise, we reach a dead end, in which case ???

We must reach one of these conclusions since the graph is finite.

  • $\begingroup$ Uhm, the (c) doesn't look a very convincing proof to write on an university test paper. Do you think my (c) answer in edited question is fine too? $\endgroup$ – Angelo Tricarico Jan 23 '14 at 22:15
  • $\begingroup$ It would be a forest in general. But you'll still need to prove that a non-empty forest has a vertex of degree 1 (rather than just claim it). $\endgroup$ – Rebecca J. Stones Jan 23 '14 at 22:19
  • $\begingroup$ Every forest is made of trees and every tree has at least 1 leaf, and the leaf is a 1-degree vertex for definition. Is this not a valid proof? $\endgroup$ – Angelo Tricarico Jan 23 '14 at 22:22
  • 1
    $\begingroup$ How do you know that every tree has at least 1 leaf? $\endgroup$ – Rebecca J. Stones Jan 23 '14 at 22:23
  • $\begingroup$ Because a tree is for definition or an empty graph, or a 1-vertex tree (which is a leaf) or n-vertexes tree with no cycles. $\endgroup$ – Angelo Tricarico Jan 23 '14 at 22:30

Hints to help you figure the answers out:

a) Two distinct paths form a cycle

b) Look at the bridges of Königsberg

c) with no dead-end, you can always continue to explore new vertices.

  • $\begingroup$ Yes dkuper, as I said, all those problems are obvious to me, but I can't manage to provide a mathematical proof. $\endgroup$ – Angelo Tricarico Jan 23 '14 at 21:38
  • 1
    $\begingroup$ Try to write the arguments why it is obvious (I don't find it so obvious, require some explanations), if you are clear these are mathematical proofs. Put them in your questions so people can confirm your arguments are valid. $\endgroup$ – Denis Jan 23 '14 at 21:41

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.