Given two graphs $G_1$ and $G_2$, which of the following conditions is sufficient to conclude that $G_1$ and $G_2$ are not isomorphic?
$|V(G_1)|\neq|V(G_2)|$
$|E(G_1)|\neq|E(G_2)|$
$G_1$ and $G_2$ have different ordered degree sequences.
Each of the presented answers is sufficient.
See lecture 2-2 slide 8.
Which of the following sequences is not grapic?
$[3,3,2,2,2]$
$[4,2,2,1,1]$
$[4,4,4,4,4]$
$[5,4,4,3,2]$
See lecture 2-2 slide 10.
Let $G=(V, E)$ be a given graph, which of the following statements is true?
$G$'s adjacency matrix is symmetric if and only if $G$ is simple.
$G$'s incidence matrix always needs less storage compared to $G$'s adjacency matrix.
All diagonal elements in $G$'s adjacency matrix are zero; i.e. $\forall u \in V(G)$, we have that $A[u,u]=0$, where $A$ denotes the $G$'s adjacency matrix.
Generally speaking, $G$'s incidence matrix is less efficient than $G$'s adjacency matrix answering the following type of questions: Given two vertices $u,v \in V(G)$, is there an edge in $G$ between $u,v$?
Suppose we are given $n \ge 1$ fixed vertices in the place. At most how many different simple graphs with this set of vertices can exist?
$\frac{n(n-1)}{2}$
$\frac{n(n+1)}{2}$
$2^{ \frac{n(n-1)}{2} }$
$2^{ \frac{n(n+1)}{2} }$
Which of the following sentences is false?
Given a graph $G$, sum of all elements in $G$'s adjacency matrix equals to twice the number of edges in $G$.
Given a graph $G$, for any two vertices $u,v \in V(G)$, any $(u,v)$-path in $G$ is also a $(u,v)$-walk in $G$.
Given three graphs $G_1$, $G_2$, $G_3$, if $G_1$ and $G_2$ are isomorphic and $G_2$ and $G_3$ are isomorphic, then $G_1$ and $G_3$ are also isomorphic.
There are 10 people in a party. Five of the people in the party know exactly 3 other people in the party. The other 5 people must know at least 3 other people in the party.