Thread: graph theory problem

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.

Hi girlie,

(a) depends on what kind of world you live in. If there's only one person in the world the statement is false. So let's suppose there are at least two (and finitely many) people in the world. That is, our graph has vertices. For every vertex , there are possible values of : namely . Assume, for contradiction, that no two vertices have the same degree. Then, since there are vertices and possibilities for a degree, we can number the vertices such that the first vertex has degree 0, the second vertex has degree 1, the third vertex has degree 2,..., the -th vertex has degree . But now we see there is no graph with these degrees of vertices: since the first vertex has degree 0, the -th vertex can have degree at most , a contradiction.

(b) You have this correct. I wanted to add "Vertices of even degree don't play no role as to parity of SUM(deg(v))" but I guess it is too obvious.

(c) Suppose there are exactly two vertices of odd degree in and there's no path connecting them. Then the connected component of containing the vertex doesn't contain . So is a graph that contains exactly one vertex of odd degree (this is where we applied the theorem you mentioned). But this contradicts part (b).

thanks so much for the help!!