Original problem:
Let a $\Gamma$ be a set of all graph's G following rules: $V_G \subset \mathbb{N}$, $|E_G| = 303$ and $G$ has $151$ vertices of degree $3$. (Last condition means that G can have more vertices of other degrees.) Decide and argument which of these following statements are true:
a) Graph $G\in \Gamma $ is connected if and only if $G$ is a tree.
b) If $G\in\Gamma$ has a vertex of a degree $7$, then $G$ is not a tree.
c) If $G\in\Gamma$ is disconnected and does not have any isolated vertices, then $G$ has a cycle.
My thoughts:
a) I know that a tree is connected. I also know that for a graph to be connected it has to have an edge between each neighboring vertices. So I think for that answer it might be a no, because some other graphs could possibly be connected?
b) A tree has $|E_G| + 1 = |V_G|$, so it must have $|V_G| = 304$. And then it is not possible to construct a tree following the rules. Because every two vertices in a tree are connected exactly one path. So to have a tree with $151$ vertices of a degree $3$ we would need at least $151 * 3 + 1$ edges, and thus it would not satisfy condition of $|E_G| = 303$.
c) So to have a cycle we need all vertices in that cycle of a degree 2. But I'm not really sure on how to go further.
EDIT:
a) Is not true.
Here is how a graph with 151 vertices of degree 3, 2 vertices of degree 2 (lower right sub-graph) and 269 edges looks like:
graph with 151 vertices of degree 3
so we need to add 303 – 269 edges to met all conditions which we can do in following way:
full graph with met conditions
We have showed that the graph is connected and is not a tree
b) Is true.
- A tree has $|E_G| + 1 = |V_G|$, so it must have $|V_G| = 304$.
- A sum of all degrees in a tree is $2 * |E_G| = 606 $
- A tree can have at most $\lfloor \frac{n-2}{k-1}\rfloor – 1$ degrees of a degree k and n number of vertices.
In our case it is $\lfloor \frac{304}{2} – 1 \rfloor = 151$
If a tree has 151 vertices of a degree 3, then sum of these degrees is 151 * 3 = 453, so we are left with 606 – 453 = 153 degrees among 304 – 151 = 153 vertices. Which is not possible to construct a tree with a vertex of degree 7 anymore.
c) Still not sure how to approach.
Are my thoughts correct? If not, what am I doing wrong?
Best Answer
I would suggest this counterexample to problem (a). Let $C_{151}$ be a cycle of order $151$ and $u_i$ be its vertices. Let two additional vertices $v$ and $w$ other than $u_i$ be chosen. Now construct graph $G$. Its vertices $V(G)=\{u_i,v,w\mid i=1,\ldots,151\}$. Its edges are edges of the cycle $C_{151}$ and still $u_iv$, $i=1,\ldots,151$, $vw$.
Consequently, graph $G$ has $303$ edges, $151$ vertices of degree $3$, is obviously connected, and not a tree, since it has a cycle.
The solution (b) is generally correct, but it is incomplete. So, if $G$ is a tree, then besides $151$ vertices of degree $3$, there must be $153$ other vertices of degree $\geq1$. Let's denote these additional vertices by $x_i$, $i=1,\ldots,153$. Since $\sum_{i=1}^{153}\operatorname{deg}(x_i)=153$ and $\operatorname{deg}(x_i)\geq1$, it follows that $\operatorname{deg}(x_i)=1$ for all $i$. So if $G$ is a tree, then it has vertices of degree $3$ and $1$, but not $7$.
Now, it is easy to answer question (c). Indeed, suppose $G$ is disconnected and does not have any isolated vertices and has no cycles. Then each component of graph $G$ is a tree. Denote these trees by the symbol $T_i$, $i=1,\ldots,k$, and $k\geq2$. Let still $t_i$ be the number of vertices of degree $3$ in $T_i$. By assumption we have: \begin{align*} &\sum_{i=1}^k t_i=151,\\ &\sum_{i=1}^k|E(T_i)|=303,\\ &\sum_{i=1}^k|V(T_i)|=\sum_{i=1}^k(|E(T_i)|+1)=303+k,\\ &\sum_{i=1}^k(|V(T_i)|-t_i)=303+k-151=152+k>153,\\ &606=\sum_{i=1}^k\sum_{x\in T_i}\operatorname{deg}(x)=\sum_{i=1}^k3t_i+\sum_{i=1}^ks_i=453+\sum_{i=1}^ks_i,\\ &\Rightarrow\ \sum_{i=1}^ks_i=153. \end{align*} where $s_i$ is the sum of degrees of those vertices $T_i$ whose degree is different from three.
So we have at least $154$ vertices whose sum of powers is $153$. Contradiction.