Graph Theory: Please help with these proofs.

Elesar · **Joined:** Wed, 6 Apr 2011 10:17:04 UTC **Posts:** 1

I need to formally proof the following. Please help.

1) Prove that if G is a graph with vertices with minimum degree bigger or equal to two, then G contains a cycle.

2) Prove that every graph G has a path of length equal to the minimum degree of all its vertices.

Any assistance would be appreciated.

outermeasure · **Posted:** Wed, 6 Apr 2011 11:55:21 UTC

Elesar wrote:

I need to formally proof the following. Please help.

1) Prove that if G is a graph with vertices with minimum degree bigger or equal to two, then G contains a cycle.

2) Prove that every graph G has a path of length equal to the minimum degree of all its vertices.

Any assistance would be appreciated.

(1) Really? What about $V(G)=\mathbb{Z}$ and $E(G)=\{\{n,n+1\}\mid n\in\mathbb{Z}\}$ ?

(2) Construct such a path.

daveyinaz · **Joined:** Sat, 16 Aug 2008 04:47:19 UTC **Posts:** 208

outermeasure wrote:

Elesar wrote:

I need to formally proof the following. Please help.

1) Prove that if G is a graph with vertices with minimum degree bigger or equal to two, then G contains a cycle.

(1) Really? What about $V(G)=\mathbb{Z}$ and $E(G)=\{\{n,n+1\}\mid n\in\mathbb{Z}\}$ ?

Sometimes a graph, perhaps in the context of this OP, is considered to only be referring to a finite number of vertices.

Shadow · **Posted:** Thu, 7 Apr 2011 22:49:15 UTC

daveyinaz wrote:

outermeasure wrote:

Elesar wrote:

I need to formally proof the following. Please help.

1) Prove that if G is a graph with vertices with minimum degree bigger or equal to two, then G contains a cycle.

(1) Really? What about $V(G)=\mathbb{Z}$ and $E(G)=\{\{n,n+1\}\mid n\in\mathbb{Z}\}$ ?

Sometimes a graph, perhaps in the context of this OP, is considered to only be referring to a finite number of vertices.

Perhaps, but perhaps not. He needs to say something to that end if that's what he means.

Matt · **Joined:** Wed, 1 Oct 2003 04:45:43 UTC **Posts:** 9632

Most applications involve a finite number of vertices. Only research mathematicians would consider infinitely many, so we should always consider the finite case as primary on the Cyberboard.

S.O.S. Mathematics CyberBoard

Graph Theory: Please help with these proofs.

Who is online