4
$\begingroup$

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:

  1. 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.
  2. 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.

$\endgroup$
1
  • 1
    $\begingroup$ Your proof using the argument about the number of edges is almost correct. The theorem says that a connected graph with $n$ vertices and $n - 1$ edges is a tree. The second one is not correct as you have written it, because it is not true that every bipartite graph is acyclic (e.g., $C_4$ is a cycle and is bipartite). It is only true that bipartite graphs cannot contain odd cycles [cycles of odd length]. In fact, a graph is bipartite if and only if it contains no odd cycles. You can use this fact (with some additional reasoning) or some other argument to show that $G$ is acyclic. $\endgroup$
    – M. Vinay
    Commented Jul 1, 2016 at 16:56

1 Answer 1

2
$\begingroup$

To prove that the graph doesn't have a cycle, note that we only have one vertex with degree greater or equal to $2$. Since in a cycle every vertex in it has a degree greater or equal to $2$ (since we have to both "enter" and "exit" the vertex) we can't have a cycle.

$\endgroup$

You must log in to answer this question.

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