3
$\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
    $\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 Jul 1 '16 at 16:56
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.