1
$\begingroup$

I am new to inductive proofs in general, and brand new to graph proofs.

I am looking for an efficient way to declare that the induced subgraph prior to application of induction is, in fact, a tree. This is an intermediate step and not really the "heart" of the proof. But I have to do it like 3-4 times (by hand) in an hour (and I'm a lefty), so I need this part to be quick and solid.

Just to outline a typical situation, consider:

$$ \text{Trees are bipartite. }\\ \text{Proof by induction. }\\ \text{ skipping base case, go to graph } T_{n+1} \text{ on } n+1 \text{ vertices. } $$

Note that there are two leaves, grab one of the leaves, and split $T_{n+1}$ into $T_{n+1} = T_n \cup T_2$, where $ T_2$ is the induced subgraph of a leaf vertex and its neighbor, and $T_n$ is the induced subgraph of everything else, since the distinct vertex of $T_2$ is a leaf.


Now, my question: what is the quickest, most efficient way (fewest words, but at sort of an elementary level, using the same/similar facts in the long winded statement below) to declare that $T_n$, so chosen, on $n$ vertices is, in fact, a tree? The rules are: I know that 1) trees have unique paths, 2) trees are connected, 3) trees are acyclic, 4) $T_{n+1}$ is a tree, and 5) $T_2$ is a tree since it is an isomorph of the base case, $n=2$. Probably some other facts in there, but I guess those are what I can think of for now.


Here is what I've got so far:

Show $T_n$ is a tree. $T_n$ is an induced subgraph of $T_{n+1}$ on all vertices sans $w$ (what I named the leaf vertex), so all connections and paths in $T_{n+1}$ which do not use edge $\{v,w\}$ are present in $T_n$. There are no paths which use edge $\{v,w\}$ save those that start or end at $w$, since $w$ is a leaf. Further, all such paths must pass through $v$ (what I named $w$'s neighbor)...and since $v$ is present in $T_n$, $T_n$ is still connected.

Also, $T_n$ is acyclic, since it is the product of the removal of edges and nodes from $T_{n+1}$. Since $T_{n+1}$ is acyclic, and since removal of edges and nodes cannot produce a cycle, $T_n$ is acyclic.

Thus, since $T_n$ is acyclic and connected, it is a tree.


I am by no means sure that I've demonstrated that $T_n$ is a tree in the paragraphs above. I tried to be quick this time, and some of my other versions are longer. I have a picture...but I'm not sure that I should put it up, since it makes it look trivial...and I have to somehow support the picture with a factual statement.

Also, every line counts. I need to be able to "show 'blank' is a tree" three times...and if it takes 5-10 minutes to write each time, I'm screwed. A quick, pithy, "show it's a tree because of a,b,c. a. b. c. therefore its a tree. Ta da!" would be awesome.

In every proof, I'm grabbing either a leaf or a branch of a tree, and grouping the rest of the graph into 1 or 2 induced subgraphs...and all I'm ever showing is connectedness and acyclicness of the subgraphs so I can use the induction assumption on them.

$\endgroup$
2
  • $\begingroup$ Trees are connected and acyclic. If you can show that removing any existing edge in a graph $G$ divides $G$ into disconnected components AND adding any edge to $G$ creates a cycle, then it follows that $G$ must be a tree. $\endgroup$
    – eyedropper
    Mar 7, 2016 at 23:17
  • $\begingroup$ Ok, that is really good for proving G is a tree. I think it is, stylistically, what i need. But I have $G$. I know it's a tree. Next, I remove an edge. Now I have component $A$ and component $B$, unconnected. Show $A$ and $B$ are each trees based on the fact that $G$ was a tree... $\endgroup$
    – Chris
    Mar 7, 2016 at 23:20

1 Answer 1

2
$\begingroup$

If you already know that $G$ is a tree, then it must follow that any two components obtained by removing a certain edge from $G$ are also trees.

To see this, suppose that $A$ is not a tree. This means that $A$ is not connected or has cycles (or both). Join $A$ to $B$ in a way to obtain $G$. Then $G$ will be disconnected or have cycles if $A$ does, and thus $G$ is not a tree, which contradicts the initial hypothesis that $G$ is a tree.

Therefore, we deduce that any two subgraphs obtained by removing an edge from a tree are also trees.

$\endgroup$
1
  • $\begingroup$ That is a good one. Thanks man. $\endgroup$
    – Chris
    Mar 8, 2016 at 2:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .