My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum

LinkBack Thread Tools Display Modes
May 28th, 2008, 03:38 AM   #1
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.
conjecture is offline  
May 28th, 2008, 06:30 AM   #2
Senior Member
Joined: Oct 2007
From: Chicago

Posts: 1,701
Thanks: 2

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.
cknapp is offline  

  My Math Forum > College Math Forum > Applied Math

cutvertex, degree, tree, vertex

Thread Tools
Display Modes

Similar Threads
Thread Thread Starter Forum Replies Last Post
Diagonal from 4 vertex unwisetome3 Algebra 3 April 5th, 2012 09:51 AM
Convert vertex to measurement haniftaj Computer Science 2 December 18th, 2010 04:07 AM
3D vertex john672 Algebra 0 November 18th, 2010 08:01 AM
numbers and vertex Recycle98 Algebra 1 March 18th, 2010 11:56 AM
Finding the Vertex l flipboi l Algebra 7 November 24th, 2009 11:34 AM

Copyright © 2017 My Math Forum. All rights reserved.