Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
1  
@Vincent: We usually use a comma rather than a semicolon, so $\{a,b\}$. –  Tara B May 1 '12 at 12:30

1 Answer 1

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.

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.