# Graph theory - A type of undirected simple finite graphs

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<a<b, \; a,b \in \mathbb{Z})$. 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.

-
What does the notation $\{a; b\}$ mean? Is that a two-element set, or an uninterrupted range of integers? –  Peter Taylor May 1 '12 at 9:35
@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. –  Tara B May 1 '12 at 9:38
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? –  user30361 May 1 '12 at 10:07
@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. –  Vincent J. Ruan May 1 '12 at 11:14
@Vincent: We usually use a comma rather than a semicolon, so $\{a,b\}$. –  Tara B May 1 '12 at 12:30

## 1 Answer

In a graph with no cycle, the number of vertices, $v$, exceeds the number of edges, $e$, by 1. If you have $s_1$ vertices of degree 1, and $s_4$ of degree 4, then $v=s_1+s_4$, and $2e=s_1+4s_4$. Put those together with $v=e+1$ and you should get your condition on $s_1$ and $s_4$.

If there's exactly one cycle, then $v=e$. Proceed as before.

If you have $s_a$ vertices of degree $a$, and $s_b$ of degree $b$, make the obvious adjustments to the arguments above.

-
In a connected graph with no cycle, $v = e + 1$. –  Kundor Apr 20 '13 at 19:43