# Number of graphs with restrictions

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.

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$.

• thanks for the answer. I didn't understand the first paragraph though.. and what on my assumption is actually wrong? :( Oct 11 '16 at 21:15
• 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? Oct 11 '16 at 21:19
• @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$. Oct 11 '16 at 21:20
• @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. Oct 11 '16 at 21:23
• @BrianM.Scott can you generalize solution for any N please? When you counting complementary graphs, this part. This is my question math.stackexchange.com/questions/4052384/… Mar 7 at 13:51