CS137: Assignment 2 Solutions - Graph Theory Problems, 2019

This document contains the solutions to CS137 Assignment 2, focusing on graph theory. The solutions address three exercises. Exercise 1 involves proving properties of a tree T based on the degree of a vertex and the maximum degree of the tree, demonstrating that there are at least d leaves. Exercise 2 explores vertex degrees in a graph, proving that if all degrees are distinct, the graph must have a vertex with degree 0 and a vertex with degree m-1, which is unattainable, and that there are m-1 possible values for all d. Exercise 3 delves into hypergraphs, proving the existence of a 2-coloring lacking monochromatic edges and deriving an upper bound for the size of a monochromatic set using a probabilistic argument. The solutions are well-structured and include references to relevant literature.

Solution to exercise 1
Given that V is a vertex and its degree is d ≥ ∆(T ). For each edge VE incident to V, use the
lengthiest path beginning with VE. Applying maximality, the vertex at the extreme of the path is
a leaf (Artur Czumaj, 2015). Applying the same to each of the d edges incident to V, we obtain d
paths beginning at V. They are disjoint except for V. the disjoint cuts off the cycle path and
makes it incomplete. Hence, every single path provides a dissimilar leaf, and we obtain d ≥ ∆(T )
leaves.
Solution to exercise 2
Every V of the graph on m vertices has0 ≤ d ≤ m−1. In instances where all the degrees (d)
differed in the graph G. The graph G must be composed of vertex of degree i for a i=0,1 … . .
contrarily, the vertex of d=0 is not neighbouring to all other vertices of G and the vertex of
d=n−1 is neighbouring to another vertices of G which is unattainable (Edward R. Scheinerman,
2013). Therefore, only m−1 possible values for all d are attainable. In either case, m vertices and
m−1 possible values for d.
Solution to exercise 3
a)
Take H=(V , E) to be an d-uniform hypergraph with ¿ 2d −1 edges. Using two colours, randomly
colour V. For every edge e ∈ E take Ae to represent the event that the edge e is
unicolor/monochromatic (West, 2017).
It is open that
Pr ( Ae ) =21−d
Hence,
Pr ( ¿ e ∈ E Ae ) ≤ ∑
e∈ E
Pr ( Ae )< 1
And there exists a 2-coloring lacking unicolor/monochromatic edges.

b)
To obtain the upper bound of m we turn the probabilistic argument on its head. The sets are
randomized and the events defined by each colour. Fixing V with v and taking X to be represent
colouring of V with a points in unique colour and b=v −1 on the other. Taking S ⊂V to
represent the uniformly selected m-set. We have;
Pr (S isunicolor under X)= ( a
n ) +( b
n )
( v
n)
It is minimized when a=b. Hence;
Pr (S ismonochromatic under X )≥ p
p=
2 ( v
2
n )
( v
n )
For the independence of S
Pr (A X )≤ ( 1−p ) m
Since there are 2v colourings;
Pr (V X AX )≤ 2v ( 1−p )m

References
Artur Czumaj, A. G. D. K. V. L. O. P., 2015. Surveys in Combinatorics 2015. In: Volume 424 of London
Mathematical Society Lecture Note Series. s.l.:Cambridge University Press, pp. 132-176.
Edward R. Scheinerman, D. H. U., 2013. Fractional Graph Theory: A Rational Approach to the Theory of
Graphs. In: Dover Books on Mathematics. s.l.:Courier Corporation, pp. 56-77.
West, D., 2017. Introduction to Graph Theory. In: Pearson Modern Classics for Advanced Mathematics
Series. s.l.:Pearson, pp. 153-210.