1. ## Graph Theory Questions

1. There are two vertices A and B which are both adjacent to the same list of vertices. It's not important whether or not they are adjacent to each other (they may or may not be). Assume there is a third vertex C. Prove that if A is adjacent to the same vertices as B and B is adjacent to the same vertices as C, that A is adjacent to the same vertices as C.

I know this is pretty obvious when just thinking about it, but I'm not really sure how to formally prove it with a valid argument. Any suggestions?

2. You are given an adjacency matrix Y for a graph, Y^2 for the graph, and the degrees of each vertex in a graph. How can you use those to determine if every neighbor of some vertex A is also a neighbor of B? Do this testing in constant time.

I'm not really sure how to approach this one because I don't know the exact properties of adjacency matrices and what they can be used for.

Any help is appreciated.

Thanks

2. For the first one, do you know about components is a graph?
$\displaystyle \mathbb{C}_A$ is the set of all vertices, X, such that there is a path from A to X.
Thus $\displaystyle \mathbb{C}_A$ is a maximal connected subgraphs.
If $\displaystyle B \in \mathbb{C}_A \cap \mathbb{C}_C \Rightarrow \quad \mathbb{C}_A = \mathbb{C}_B = \mathbb{C}_C$.

I am not quite clear as to what you are expected to do in #2.