0
$\begingroup$

I have a few questions for a practice quiz I'm struggling with about graph theory, and I'd appreciate some clarification on my answers.

  1. What vertices are adjacent to vertex 2?

I'm guessing this means anything that's connected to 2. In this case, it'd be 0, 1, and 4, but I just wanted to make sure.

  1. What is ∑(v∈V)deg⁡(v)?

The v∈V should be a lower exponent under the sigma symbol but I couldn't figure out how to do that. I'm not really sure what this question means, so I'd appreciate some help or a push in the right direction.

  1. A clique is a subgraph G' = (V', E') that is complete (i.e., every vertex in the clique is connected to every other vertex in the clique). What is the largest clique contained in this graph? Note both the size and the vertices in V'.

I know a clique means that every vertex is connected to every other vertex. I know the triangle connecting 0, 1, and 2 is an obvious one but I'm not sure if that's the largest. I get confused with the definition of a clique when I look at larger sets. If I had to answer this question I would choose the graph formed by 0, 1, 2 and 4, but again, I'm not sure if that's the largest clique in the graph.

enter image description here

$\endgroup$
0

2 Answers 2

Reset to default
0
$\begingroup$

Regarding Q3, here's a way to keep the overview and perhaps see more easily whether there is a size 4 (or larger) clique in the graph: Every vertex in a size $\ge 4$ clique has at least degree $3$. Hence any vertices of lower degree are just obfuscating our view to find such a clique. So remove vertices $3$ and $5$ who have lower degree. After tat, $7$ has only degree $2$ left and can be removed as well. After that, we can remove vertex $6$ for the same reason and so on. In this example, we can ultimately remove all vertices and conclude that no such clique exists. (In general, this method is not guaranteed to get rid of all vertices if there is no large clique, but may at least simplify things a bit)

$\endgroup$
0
$\begingroup$

  1. Yes.

  2. The sigma here is a summation symbol. $\sum_{v\in V} \deg(v)$ means that you should sum up the degrees of all of the vertices. Do you know what the degree of a vertex is?

  3. I think you were right in your first statement about $\{0, 1, 2\}$ being the largest clique, yes. (But I’m also no graph theorist and have never dealt with cliques before — this seems correct from the given definition, though.) The graph over $\{0,1,2,4\}$ is not a clique.

$\endgroup$
3
  • 2
    $\begingroup$ Re 3: $\{0,1,2\}$ is a, not the largest clique. We can find two more triangles $\endgroup$
    – Hagen von Eitzen
    Commented Jun 4, 2019 at 5:52
  • 1
    $\begingroup$ For 2), yes I know what the degree of a vertex is. So if I were to find the degree of each vertex in the graph and add them all together, I get 24. Is that correct? $\endgroup$
    – Blackthorn
    Commented Jun 4, 2019 at 7:12
  • 1
    $\begingroup$ @Blackthorn Yes, the answer is $24$, found more easily by recalling $\sum_{v\in V}\text{deg}(v)=2e$ where $e$ is the number of edges in the graph. $\endgroup$
    – Shubham Johri
    Commented Jun 4, 2019 at 7:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .