How many Graphs with 5 vertices (a, b, c, d, e) have only one vertex with rank 4?

Question

Having trouble with the following combinatorics/graphes problem:

How many Graphs with 5 vertices (a, b, c, d, e) have only one vertex with degree 4?

I'm thinking about writing down all the possibilities, calculate the possibility of each case and sum all results. But is that the only solution?

Answer 1

If we delete the degree-4 vertex, we obtain a 4-vertex graph with maximum degree at most 2. We can count them (up to isomorphism) by hand:

(I generated the above using geng which comes with Nauty. The vertices are marked with their degrees.)

After deleting the unique degree-4 vertex, the graphs are:

• $4K_1$
• $2K_1 \cup K_2$
• $K_1 \cup P_2$ (where $P_2$ is a 2-edge path)
• $2K_2$
• $P_3$
• $K_1 \cup K_3$
• $C_4$

If we instead want the number of labeled graphs, we can sum $5!/|\mathrm{aut}(G)|$ for each graph $G$, via the Orbit-Stabilizer Theorem. This gives \begin{align*} & \frac{5!}{4!} +\frac{5!}{4} +\frac{5!}{2} +\frac{5!}{8} +\frac{5!}{2} +\frac{5!}{3!} +\frac{5!}{8} \\ = {} & 5+30+60+15+60+20+15 \\ = {} & 205. \end{align*}