My Math Forum Why can't a vertex with degree = 1 be cut-vertex in a tree?

 Applied Math Applied Math Forum

 May 28th, 2008, 03:38 AM #1 Newbie   Joined: Apr 2008 Posts: 20 Thanks: 0 Why can't a vertex with degree = 1 be cut-vertex in a tree? I read in a book that, every vertex in a tree with degree > 1 is a cut-vertex. I wonder why degree > 1 condition should be there. Even a vertex which has degree = 1 can also be a cut-vertex. Isn't it? So, could someone please explain whether I am right or that degree > 1 condition is really required. Just to make sure that there is no ambiguity in the discussion, I am adding the definitions from the book itself. The vertex connectivity of a connected graph G is defined as the minimum number of vertices whose removal from G leaves the remaining graph disconnected. A connected graph is separable if its vertex connectivity is 1. In a separable graph a vertex whose removal disconnects the graph is called a cut-vertex.
 May 28th, 2008, 06:30 AM #2 Senior Member   Joined: Oct 2007 From: Chicago Posts: 1,701 Thanks: 3 In order for a vertex to connect two different subgraphs, it needs an edge connected to each subgraph, thus it needs degree two. As a littlle "experiment" to help you grasp the concept, draw 2 (or 3 or 4 or...) graphs next to each other, and try to connect any number of them with 1 vertex. How many edges do you need? Now, try to connect any two of them with 1 edge. Can you do it using an extra vertex? The thing I don't understand is "[b]any[b] vertex with degree > 1 is a cut vertex", but it may have to do with the type of graph you're working with.

 Tags cutvertex, degree, tree, vertex

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post unwisetome3 Algebra 3 April 5th, 2012 09:51 AM haniftaj Computer Science 2 December 18th, 2010 03:07 AM john672 Algebra 0 November 18th, 2010 07:01 AM Recycle98 Algebra 1 March 18th, 2010 11:56 AM l flipboi l Algebra 7 November 24th, 2009 10:34 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top