# Discrete Maths (Degree level)

Watch
Announcements

Page 1 of 1

Go to first unread

Skip to page:

This discussion is closed.

Hi, I've got my discrete maths exam 2moro and i need some help with a few last minute crisis questions.

1. (a) State and prove the handshaking lemma

(b) What is by definition, a spanning tree of a connected graph [ = (V,E)?

(c) Write down the formal definition of a graph

(d) What is by defintion, a complete graph of order n?

(e) For which values of n does the complete graph, Kn, contain a euler trail or a hamiltonian cycle?

BIG BIG Thanks

Someone asked me why do I give up my time to send the people of TSR past papers when they want them? Well you lot are always here to help...I'm merely helping in a different way.

1. (a) State and prove the handshaking lemma

(b) What is by definition, a spanning tree of a connected graph [ = (V,E)?

(c) Write down the formal definition of a graph

(d) What is by defintion, a complete graph of order n?

(e) For which values of n does the complete graph, Kn, contain a euler trail or a hamiltonian cycle?

BIG BIG Thanks

Someone asked me why do I give up my time to send the people of TSR past papers when they want them? Well you lot are always here to help...I'm merely helping in a different way.

0

Report

#2

(Original post by

Hi, I've got my discrete maths exam 2moro and i need some help with a few last minute crisis questions.

1. (a) State and prove the handshaking lemma

(b) What is by definition, a spanning tree of a connected graph [ = (V,E)?

(c) Write down the formal definition of a graph

(d) What is by defintion, a complete graph of order n?

(e) For which values of n does the complete graph, Kn, contain a euler trail or a hamiltonian cycle?

BIG BIG Thanks

Someone asked me why do I give up my time to send the people of TSR past papers when they want them? Well you lot are always here to help...I'm merely helping in a different way.

**manps**)Hi, I've got my discrete maths exam 2moro and i need some help with a few last minute crisis questions.

1. (a) State and prove the handshaking lemma

(b) What is by definition, a spanning tree of a connected graph [ = (V,E)?

(c) Write down the formal definition of a graph

(d) What is by defintion, a complete graph of order n?

(e) For which values of n does the complete graph, Kn, contain a euler trail or a hamiltonian cycle?

BIG BIG Thanks

Someone asked me why do I give up my time to send the people of TSR past papers when they want them? Well you lot are always here to help...I'm merely helping in a different way.

(a) The handshaking lemma states that the sum of the degrees of vertices is twice the number of edges. The proof is quite self-evident: every edge has two vertices associated with it, the one it is going from and the one it is going to (well, this need not be a directed graph, but anyway ...). This means that in counting the degree of each vertex we count each edge twice. (The consequence of this is that in any graph the number of odd-degree vertices is even.)

(I suppose you need a 'real' proof, which I'm afraid I don't know; sorry.)

(b) A spanning tree of a graph is a subset of (n-1) edges that form a tree. (Ie, a spanning tree is a tree (=no cycles) which connects all vertices of the graph.)

(c) I'm not sure about a formal definition. Probably something like: a graph is a set of points (vertices) and set of lines (edges) which are connecting some subset of these points. Maybe you could define it in terms of a relation in SxS where each ordered pair represents an edge between the two points?

(d) A complete graph of order n, , is the simple graph (no loops or parallel edges) with n vertices where every vertex is connected to all other vertices.

(e) A Hamiltonian cycle for n3.

An Eulerian trail ... hmm, evidently it exists for n=1, n=2 and n=3; then it exists either as an Eulerian

**circuit**or not at all (because either there are no odd or all odd degrees; there can't be just two odd degrees). Because a complete graph has degree (n-1) for all vertices, it follows that all complete graphs of an odd order greater than 1 are Eulerian. (But this is just my conjecture; it may not be true.)

(Now this has been SO much more fun than revising for my philosophy paper 1 & 2!)

(Edit: sorry, greater than or equal to 3 for Hamiltonian)

(Oh, and do you say 'Eulerian' with /ju/ or /oj/ as the first syllable? Because I've noticed the English tend to write 'a Eulerian' rather than 'an'; isn't it a German/Swiss name, thus starting with a vowel?)

1

Report

#3

(Original post by

(Oh, and do you say 'Eulerian' with /ju/ or /oj/ as the first syllable? Because I've noticed the English tend to write 'a Eulerian' rather than 'an'; isn't it a German/Swiss name, thus starting with a vowel?)

**Sinuhe**)(Oh, and do you say 'Eulerian' with /ju/ or /oj/ as the first syllable? Because I've noticed the English tend to write 'a Eulerian' rather than 'an'; isn't it a German/Swiss name, thus starting with a vowel?)

0

Report

#4

(Original post by

Euler is pronounced 'oiler', so yeah, an 'an' should precede it.

**dvs**)Euler is pronounced 'oiler', so yeah, an 'an' should precede it.

0

Report

#5

The Edexcel D1/2 version of the formal definition of a graph is

" A Graph G consists of a finite number of points (usually called vertices or nodes) connected by lines (usually called edges or arcs.)"

- Not startling stuff!

Aitch

" A Graph G consists of a finite number of points (usually called vertices or nodes) connected by lines (usually called edges or arcs.)"

- Not startling stuff!

Aitch

0

Report

#6

(Original post by

" A Graph G consists of a finite number of points (usually called vertices or nodes) connected by lines (usually called edges or arcs.)"

Aitch

**Aitch**)" A Graph G consists of a finite number of points (usually called vertices or nodes) connected by lines (usually called edges or arcs.)"

Aitch

MathWorld gives this definition: 'In a mathematician's terminology, a graph is a collection of points and lines connecting some (possibly empty) subset of them. The points of a graph are most commonly known as graph vertices, but may also be called "nodes" or simply "points." Similarly, the lines connecting the vertices of a graph are most commonly known as graph edges, but may also be called "arcs" or "lines."'

http://mathworld.wolfram.com/Graph.html

0

Report

#7

(Original post by

What about infinite graphs? For example, the Cayley graph of an infinite group is infinite (though locally finite), I think.

MathWorld gives this definition: 'In a mathematician's terminology, a graph is a collection of points and lines connecting some (possibly empty) subset of them. The points of a graph are most commonly known as graph vertices, but may also be called "nodes" or simply "points." Similarly, the lines connecting the vertices of a graph are most commonly known as graph edges, but may also be called "arcs" or "lines."'

http://mathworld.wolfram.com/Graph.html

**Sinuhe**)What about infinite graphs? For example, the Cayley graph of an infinite group is infinite (though locally finite), I think.

MathWorld gives this definition: 'In a mathematician's terminology, a graph is a collection of points and lines connecting some (possibly empty) subset of them. The points of a graph are most commonly known as graph vertices, but may also be called "nodes" or simply "points." Similarly, the lines connecting the vertices of a graph are most commonly known as graph edges, but may also be called "arcs" or "lines."'

http://mathworld.wolfram.com/Graph.html

**pragmatic**definition, which applies to what follows, that is the D1 and D2 Edexcel content!

Aitch

0

Report

#8

(Original post by

I should suggest that the Edexcel version which I quoted above is a

**Aitch**)I should suggest that the Edexcel version which I quoted above is a

**pragmatic**definition, which applies to what follows, that is the D1 and D2 Edexcel content!
0

X

Page 1 of 1

Go to first unread

Skip to page:

new posts

Back

to top

to top