Prove the following statements. Please write out the proof in detail, without skipping any

vital step. You can use figures to illustrate your work if necessary.

a. The centre of a graph is the set of vertices with minimum eccentricity. Show that a

tree can have either (i) exactly one vertex as a centre or (ii) two vertices as centres,

and these vertices will be connected by an edge

b. If a tournament is transitive then there is a path that visits every vertex exactly

once

c. A hypercube only has cycles of even length

d. If two distinct cycles in a graph have a common edge, e, then there exists a cycle in

the graph that does not have the edge e

e. A graph and its complement cannot both be disconnected

f. Let there be a graph with 2m vertices containing no triangles. Prove that the

number of edges in such a graph can be at most m2

g. In a tree all nodes, except the leaves will have betweenness centrality greater than

zero