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.


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?

  • $\begingroup$ I have to disappoint you, but you did not give a single correct answer. You don't know what a connected graph is, nor do you know Handshaking lemma. $\endgroup$
    – kabenyuk
    Jan 7 at 15:23
  • $\begingroup$ You should note that if there are $303$ edges then the sum of the degrees of all the vertices is $2*303$. So your impossibility argument for there being a tree on 304 vertices with 151 vertices of degree 3 does not work as it stands. $\endgroup$ Jan 7 at 15:34
  • $\begingroup$ I would start with the fact that $303$ edges have $606$ ends and the $151$ vertices of degree $3$ mentioned only account for $453$ of them. There is a lot of flexibility left, so any statement that says the graph must be some way is false. I would try to construct examples that violate the desires. It shouldn't be hard. Note that the vertices in a cycle may have degree higher than $2$-you just need a path that closes to have a cycle. $\endgroup$ Jan 7 at 15:51
  • $\begingroup$ @RossMillikan and Jamie Radcliffe thank you for your helpful comments. I have edited my thought, hopefully they are at least partially right now. I'm still unsure how to approach problem c). $\endgroup$
    – popcorn
    Jan 7 at 19:54
  • $\begingroup$ @popcorn However, your graph in the picture has vertices of degree $4$ and vertices of degree $3$ less than required. $\endgroup$
    – kabenyuk
    Jan 8 at 5:16

1 Answer 1


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.

  • $\begingroup$ Everything is clear now, thank you for your time and that solution. $\endgroup$
    – popcorn
    Jan 8 at 10:31
  • $\begingroup$ You're welcome. $\endgroup$
    – kabenyuk
    Jan 8 at 11:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .