This discussion is closed.
manps
Badges: 0
Rep:
?
#1
Report Thread starter 16 years ago
#1
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 :tsr:

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
Sinuhe
Badges: 8
Rep:
?
#2
Report 16 years ago
#2
(Original post by 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 :tsr:

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.
OK, I'm only doing the IB, so this may not be what you need at university level. Well, it very probably isn't, since I'm in secondary school, but anyway:

(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, \kappa_{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 n\ge3.
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
dvs
Badges: 10
Rep:
?
#3
Report 16 years ago
#3
(Original post by 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?)
Euler is pronounced 'oiler', so yeah, an 'an' should precede it.
0
Sinuhe
Badges: 8
Rep:
?
#4
Report 16 years ago
#4
(Original post by dvs)
Euler is pronounced 'oiler', so yeah, an 'an' should precede it.
Thanks - I thought so. But the IB always tend to write, for some reason, 'a Eulerian trail' (or circuit or graph), in exams as well as in their 'terminology notes' for graph theory. I thought it was very curious that they should do so. Oh well, I don't think they'll take away points for writing 'an Eulerian'.
0
Aitch
Badges: 2
Rep:
?
#5
Report 16 years ago
#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
0
Sinuhe
Badges: 8
Rep:
?
#6
Report 16 years ago
#6
(Original post by 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
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
0
Aitch
Badges: 2
Rep:
?
#7
Report 16 years ago
#7
(Original post by 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
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!

Aitch
0
Sinuhe
Badges: 8
Rep:
?
#8
Report 16 years ago
#8
(Original post by 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!
Sorry, I have only a vague idea of what A-levels look like; I suppose D1 and D2 are introductory content then. I didn't mean to sound rude so I apologise if I came across as being such. Infinite graphs are just something we mentioned when doing the abstract algebra option (sets, relations and groups).
0
X
new posts
Back
to top
Latest
My Feed

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

Personalise

Has your education been disrupted this academic year due to the pandemic?

Yes (37)
88.1%
No (5)
11.9%

Watched Threads

View All
Latest
My Feed