Graph Theory - Introduction Questions

Question

I have a couple of questions that are probably SUPER easy for anybody that has studied graph theory but are confusing the hell out of me. I know it may be inconvenient to help me but I have a test coming up and I'm really confused.

Question 1: If there are 2 vertices that have the same neighborhood, then which statement must hold?

1) Both vertices will be of deg zero?

2) The deg of every vertex will be even?

3) There is an edge between the two vertices?

4) There cannot be an edge between the two vertices?

I thought that it was #3 but it wasn't.

Question 2: Consider a graph G with vertices {v1, v2, v3, v4} and edges {(v1,v2), (v2,v3), (v1,v3), (v2,v4)} What is the degree of v3?

1) 2

2) 4

3) 3

4) 1

Question 3: G = ({v1, v2, v3, v4, v5}, {(v1,v2), (v2,v3),(v3,v4), (v4,v5),(v5,v1),(v2,v4),(v2,v5)}) Which of the following is NOT a subgraph of G?

1) G' = ({v1, v2, v3, v4, v5}, {(v1,v2), (v2,v3),(v3,v4), (v4,v5),(v5,v1)})

2) G' = ({v1, v3, v4, v5}, {(v3,v4), (v4,v5),(v5,v1), (v2,v4)})

3) G' = ({v1, v2, v3, v4, v5}, {(v1,v2)})

4) G' = ({v2, v4, v5}, {(v4,v5),(v2,v4),(v2,v5)})

Answer 1

Hints:

• Question 1: Note that the neighbourhood of a vertex is the set of vertices that are connected to it plus all the edges that connect those vertices among themselves. A vertex does not belong to its own neighbourhood. If there is an edge between two vertices then they are definitely in the neighbourhood of each other. What would that imply?
• Question 2: What's the degree of a graph? You just have to count.
• Question 3: A subgraph is formed by a subset of the original vertex set plus all the edges that connect those vertices amongst themselves. Alternative 2) has an edge that, even though it belongs to the original graph, does not connect the selected vertices of the subgraph.