# Graphs with a given number of edges and vertices of degree $3$

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?

• 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. Jan 7 at 15:23
• 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. Jan 7 at 15:34
• 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. Jan 7 at 15:51
• @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). Jan 7 at 19:54
• @popcorn However, your graph in the picture has vertices of degree $4$ and vertices of degree $3$ less than required. Jan 8 at 5:16

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.