Scribd
Upload
30 views1 page

Pset 2 C

The document discusses two graph theory problems. [1] For the first problem, it shows that the minimum number of edges in a graph is the sum of the number of vertices in each connected component minus the number of components. [2] For the second problem, it proves by induction that any tree with a vertex of degree k+1 will contain at least k+1 leaves. It does this by removing an edge to split the tree into two components and showing that reconnecting them adds another leaf.

Uploaded by

songsiyuan0329
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
30 views1 page

Pset 2 C

The document discusses two graph theory problems. [1] For the first problem, it shows that the minimum number of edges in a graph is the sum of the number of vertices in each connected component minus the number of components. [2] For the second problem, it proves by induction that any tree with a vertex of degree k+1 will contain at least k+1 leaves. It does this by removing an edge to split the tree into two components and showing that reconnecting them adds another leaf.

Uploaded by

songsiyuan0329
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Pset 2a

Siyuan Song
July 18, 2023

1 Problem 6
Suppose the components of the graph G are G1 , G2 , ...Gk and they have a1 , a2 , ..., ak vertices. The
number of edges in each component is e1 , e2 , ..., ek According to the problem,

a1 + a2 + a3 + ... + ak = n

Each component is a connected graph with at least a spanning tree. According to Euler formula
and the feature of trees, the components must have em ≥ am − 1. In this condition, we have
k
X
ei ≥ n − k
i=1

and this sum is the number of edges in the graph G.

2 Problem 7
Let us prove by doing induction.

Base case: The Graph G has Two vertices and an edge connecting them. Definitely, we have 2
leaves, which is greater than 1 (the largest degree).

Suppose we have a tree T with a vertex q whose degree is k+1. Remove one of the edges and get
two components. One of the components is a graph G’ and the vertex q has a degree of k. The other
component is another tree T’ (as it is connected and there are no cycles).
Induction hypothesis: There are at least k leaves in graph G’.

Induction step:
in the original tree T, one of its subgraph is T’+{q}, which is also a tree according to the growing
[Link] to leaf lemma, there must be at least two leaves in this tree, which means there is
another leaf other than q. Therefore, after we connect the two components G’ and T’ and get G, we
have at least one more leaf than in G’.
This indicates that there are at least k + 1 leaves in the tree where there is a vertex q whose degree
is k + 1.
This is how we finish the induction.

You might also like