I'm a discrete math student and I've bumped into the following question. I tried to prove it and specifically in first part I thought of two ways of proving it. but in each of the ways the proof looks really short without much of information, so I'm afraid I forgot something or did something wrong. I would appreciate your advice and help
"let G be a simple graph above vertices {1,2,...,n} while $n\ge3$ and $n\in N$. furthermore, vertex number 1 is of degree $n-1$ and every other vertex is of degree 1. Prove G is a tree graph."
Proof:
Prove that G is a connected graph: let's notice that the graph is a "star graph" because the graph is a simple one (meaning no loops and multiple edges) and the first vertex is of degree $n-1$, while there're n vertices. meaning the vertex of degree $n-1$ is connected to the rest of $n-1$ neighbours. So as we see there's a path between each two vertices in G -> G is connected graph.
- another way I thought of: from the degrees theorem: $2|E|=\Sigma v_i=(n-1)*[1]+[n-1]=2n-2 \to |E|=n-1$ and there's a theorem that tells that a graph with n vertices and n-1 edges is a connected graph.
Prove that G is a graph without cycles: let's notice that G is isomorphic to a Bipartite graph while vertices of degree 1 are group A of vertices and the vertex of degree $n-1$ is group B of vertices. and there's a theorem that tells that every Bipartite graph is acyclic graph.
from 1 and 2 we get that G is acyclic and connected graph. then by definition of tree, G is a tree graph.