3
$\begingroup$

Prove that each property below characterizes forests...

a. every induced subgraph has a vertex of degree at most one.

When proving a characterization, do we have to prove both directions, like an if and only if, or does it suffice to prove only one direction?

$\endgroup$
  • $\begingroup$ A characterization of a property P is another property Q which is equivalent to property P. This is a two-sided statement. $\endgroup$ – Yuval Filmus Oct 9 at 9:15
8
$\begingroup$

"Characterizes" means you must prove "if and only if".

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

"Characterize" means you must prove both directions.

However, you can be more efficient with multiple characterizations: proving A implies B implies C implies A shows all three are equivalent, because implication is transitive. Examples in practice:

Equivalence of induction, strong induction, and well-ordering

Equivalence of 6 different characterizations of the exponential function

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ +1, though in the OP's case that's probably not allowed: each property is probably expected to have a separate proof, and while it's probably OK for later proofs to rely on earlier results, the reverse is not true. (This is just due to the artificial nature of an educational setting like this.) $\endgroup$ – ruakh Oct 10 at 0:20
1
$\begingroup$

Welcome to CS.SE :)

Suppose $G$ is a forest. Then so is every subgraph $G[X]$ induced by some $X \subseteq V(G)$, and clearly every forest has a node of degree at most one (either an isolated vertex or some leaf).

Now suppose that $G$ is a graph such that every subgraph $G[X]$ induced by some $X \subseteq V(G)$ has a vertex of degree at most one. Then $G$ cannot contain a cycle, otherwise the vertices of said cycle would induce a subgraph where every vertex has degree at least $2$ (in a cycle, every vertex is adjacent to its two neighbors). As $G$ is acyclical, it must be a forest.

Putting the two pieces together, we get your desired result.

| cite | improve this answer | |
$\endgroup$

Your Answer

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