Math Is Fun Forum

gizmoguy19

Member

Registered: 2012-07-03

Posts: 6

Graph Theory Questions

Hello
I came across these graph theory questions from my course book, and had trouble understanding them. Any help would be greatly appreciated.

1. Given a graph that is k-regular, prove that G must have a path of at least k
2. If every vertex in a graph G has degree at least two, prove that G has a cycle

thanks

careless25

Real Member

Registered: 2008-07-24

Posts: 560

Re: Graph Theory Questions

2.

Proof By induction

Base Case:
we need atleast 3 vertices of degree 2 to have a cycle. Example a triangle.

IH: Assume true
IS:
If graph G with n vertices contains a cycle where each vertex has a degree of 2, then a graph M with n+1 vertices contains the graph G. Therefore graph M with n+1 vertices with degree 2 also contains a cycle.

QED

This is just a rough proof to give you the idea.