0
$\begingroup$

I have been given a question in graph theory recently.

let { a,b,c,d,e } be a set of 5 vertices.

How many different graphs are there, such that there's one and only one vertex with a degree of 4.

Note : we are only dealing with simple graphs.

My suggested solution as follows:

$5*2^{{4 \choose 2}}$ - choosing a vertex with a degree of 4 ( which means that it connects to all of the others). We are left with 4 vertices. The number of graphs we can keep creating are $2^{4 \choose 2}$.

Now we need to get rid of all the graphs that contain more than one vertex with a degree of 4.

From now on I focus only on the 4 vertices which weren't chosen. Note that in order to get another vertex with 4 neighbors, it needs to be connected to the rest of those which weren't chosen.

Let's mark them a1,a2,a3,a4.

Let ai - number of graphs such that vertex ai has exactly 3 neighbors ($1\le$i$\le4$)

by using inclusion-exclusion principle:

$|ai|$ = $4*2^{{3 \choose 2}}$ - choosing the vertex with 3 neighbors. for the other 3 no restrictions.

$|ai \cap aj | = {4 \choose 2}*2^{{2 \choose 2}}$

$|ai \cap aj \cap ak | = 1$ ( the complete graph on 4 vertices, since 3 vertices have 3 neighbors, the last one has 3 neighbors as well.

in total:

$$5*2^{{4 \choose 2}} - [4*2^{{3 \choose 2}}-6*2^{{2 \choose 2}}+1]= 299 $$

hence there are 299 different graphs with 5 vertices such that one and only one vertex has 4 neighbors.

Is that correct? Thanks in advance.

$\endgroup$
2
$\begingroup$

If there are $n$ graphs with $a$ as the unique vertex of degree $4$, then there are also $n$ with $b$ as the unique vertex of degree $4$, and similarly for vertices $c,d$, and $e$, so there must be $5n$ graphs altogether; $299$ is not a multiple of $5$, so it can’t be right.

Let’s count the graphs with $a$ as the unique vertex of degree $4$. Consider what’s left when $a$ and the four edges incident at $a$ are removed from one of these graphs: it’s a graph on $4$ vertices in which no vertex has degree $3$. Conversely, if I start with a graph on the vertices $b,c,d$, and $e$ that has no vertex of degree $3$, I can join each vertex to $a$ to get one of the graphs that I want. So how many graphs on $4$ labelled vertices have no vertex of degree $3$?

I find it easier to count the complementary graphs. These are the graphs on $4$ labelled vertices that have no isolated vertex, i.e., no vertex of degree $0$. There are altogether $$2^{\binom42}=2^6=64$$ graphs on $4$ labelled vertices.

  • One of them has $4$ isolated vertices;
  • none of them has exactly $3$ isolated vertices;
  • $\binom42=6$ of them have exactly $2$ isolated vertices; and
  • $4\cdot4=16$ of them have exactly $1$ isolated vertex. (Why?)

Thus, there are $1+0+6+16=23$ with at least one isolated vertex and therefore $64-23=41$ with no isolated vertex. In the notation of the first paragraph, $n=41$, and there are therefore $5\cdot41=205$ graphs on $5$ labelled vertices having exactly one vertex of degree $4$.

$\endgroup$
  • $\begingroup$ thanks for the answer. I didn't understand the first paragraph though.. and what on my assumption is actually wrong? :( $\endgroup$ – Tom.A Oct 11 '16 at 21:15
  • $\begingroup$ also : " ...that has no vertex of degree 3, I can join each vertex to a to get one of the graphs that I want". if you were to decide that a is of degree 4, then you cant join anything else to a, since it's a simple graph. or am i missing something out? $\endgroup$ – Tom.A Oct 11 '16 at 21:19
  • 1
    $\begingroup$ @Tom: Take any graph with vertex $a$ as the unique vertex of degree $4$. Now interchange vertices $a$ and $b$: you have a graph in which $b$ is the unique vertex of degree $4$. What’s more, every graph with vertex $b$ as the unique vertex of degree $4$ can be obtained in that way. Thus, there are exactly as many graphs with $b$ as the vertex of degree $4$ as there are with vertex $a$ as the unique vertex of degree $4$. The same goes for each of the vertices, so the total number of such graphs must be a multiple of $5$. $\endgroup$ – Brian M. Scott Oct 11 '16 at 21:20
  • $\begingroup$ @Tom: You’re not reading carefully. In the bit that you quote, ‘degree $3$’ refers to the degree in the subgraph that’s left after vertex $a$ has been removed (along with the $4$ edges attached to it). Vertex $a$ and its four edges aren’t even there. $\endgroup$ – Brian M. Scott Oct 11 '16 at 21:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.