The friendship graph is defined as follows: the vertices are people,
and we draw an edge between two people if they are friends. There are two kinds of people in the world: normal and strange. A normal person has an even number of friends, and a strange person has an odd number of friends.
(a) Prove that there are at least two people in the world with the same number of friends.
(b) Use the first theorem of graph theory to prove that there are an even
number of strange people in the world.
(c) If there are exactly two strange people in the world, prove that there is a path connecting them in the friendship graph.
Alright so the first theorem of graph theory is that SUM(deg(v))=2|E| where v=# vertices in the graph and E=# of edges in the graph
a) not too sure how to prove this....
b) Would this be an appropriate proof:
According to the first theorem of graph theory, the SUM(deg(v))=2|E|. Since the the people who are "strange" have an odd number of friends, that means the degree of those vertices are odd. Since adding an odd number of odd numbers together results in an odd number, and adding an even number of odd numbers together results in an even number. In order for the equation SUM(deg(v))=2|E| to hold, the SUM(deg(v)) must be divisible by two, and therefore the SUM(deg(v)) must be even. Therefore there must be an even number of "strange" people in the world.
c) I don't know what to do for this part but I know I need to use this theorem:
If Gi is a connected component of G then degGi(u)=degG(u) for any u in vi.