Let $G=(V,E)$ be a simple connected graph with only one cycle
If $G$ has four vertices of degree $2$, five vertices of degree $3$, three vertices of degree $4$, one vertex of degree $5$, how many pendant vertices does $G$ have if $\Delta = \text{max}\{\text{deg}(v)|v\in V\} = 5$?
My approach was to take the unique cycle (not necessarily on $6$ vertices like below) and open it:
to then get a tree.
We are essentially dividing a vertex in two, thus there are $|V|=4+5+3+1+\color{red}{1}+p=14+p$ vertices, where $p$ is how many pendant vertices there are in the original graph.
As per the edges $\sum\limits_{v \in V} \text{deg}(v) = 4\cdot 2 + 5\cdot 3 + 3\cdot 4 + 1\cdot 5 \color{red}{-1 +1} +p= 40+p=2|E|$
Then since we are working with a tree $2|V|=2|E|+2$, and $28+2p=40+p+2$, $p=14$.
I could be wrong though, I do not feel confident about my approach. How does one go about working this problem?
Best Answer
I think your approach is perfectly fine (I would say it is clever actually). With the very same argument, one can show that if a simple connected graph $G$ has exactly one cycle, then $|V(G)| = |E(G)|$ (because when we open a cycle and get a tree, we increment the number of vertices by $1$ while keeping the number of edges same). Having said that, we can write
$$\sum\limits_{v \in V(G)}d(v) = 4\cdot 2 + 5\cdot 3 + 3\cdot 4 + 1\cdot 5 +p= 40+p=2|E(G)|=2|V(G)|$$
Then, since $|V(G)| = 4+5+3+1+p = 13+p$, we get $40+p = 2(13+p) \implies p = 14$ as you suggested. But as I said, the result $|V(G)| = |E(G)|$ when $G$ has only one cycle uses the very same argument that you used to find your result directly, so I am not adding much to your solution.