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
    Sorry, Rya$n$, but the majority of graph theory proofs are i$n$ductive! 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

2

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.

  • 1
    In a *connected* graph with no cycle, $v = e + 1$.2013-04-20