2
$\begingroup$

When studying Organic Chemistry, I just came up with a problem, which is following:

Problem 1: Let $T$ be the set of undirected simple finite graphs $G(V,E)$ satisfying that $\forall v \in V,$ $\deg(v) \in \{1;4\}$. In each case below, find necessary and sufficient conditions of $S_1(G)$ and $S_4(G)$ so that $G \in T$, assuming $S_i(G)$ is the number of vertex $v$ of $G$ such that $\deg(v)=i$:

a) $G$ has no cycles.

b) $G$ has exactly $1$ cycle.

I have a solution using induction, which is not pure to me. I'm seeking for the original solution. While on the way, I has slightly generalized the problem and gained:

Problem 2: Let $T$ be the set of undirected simple finite graphs $G(V,E)$ satisfying that $\forall v \in V,$ $\deg(v) \in \{a;b\}$ $(0. In each case below, find necessary and sufficient conditions of $a$, $b$, $S_a(G)$ and $S_b(G)$ so that $G \in T$, assuming $S_i(G)$ is the number of vertex $v$ of $G$ such that $\deg(v)=i$:

a) $G$ has no cycles.

b) $G$ has exactly $1$ cycle.

Anyone has any ideas to solve either the first or the second problem (purely and originally), please share. Thank you.

P.S: Sorry for my bad English.

  • 0
    What does the notation $\{a; b\}$ mean? Is that a two-element set, or an uninterrupted range of integers?2012-05-01
  • 0
    @Peter: Since this question comes from organic chemistry, I would very much assume it's a two element set, and this is about putting together a bunch of carbon atoms.2012-05-01
  • 0
    @Peter: It's a two-element set. I really don't know how to improve the notation because I usually use $\overline{a,b}$ to express an uninterrupted range of integers.2012-05-01
  • 1
    @Vincent: We usually use a comma rather than a semicolon, so $\{a,b\}$.2012-05-01
  • 0
    Sorry, Ryan, but the majority of graph theory proofs are inductive! Given the expanding nature of graphs, we tend to see induction as the logical way to prove results in general that are clearly provable in specific cases(often initially by exhaustion). Anyone got a non-inductive proof?2012-05-01

1 Answers 1