A question on bipartite graph

165 Views Asked by At

So I've been asked to find how many vertices are there on $G$. $G$ is a bipartite graph of order $n$ partitioned to $A$ and $B$ where $A$ has an order of $10$ which every vertex in $A$ has degree $6$. In $B$, $4$ vertices with degree $2$ and $3$ vertices with degree $4$. All other vertices in $G$ have degree $8$. Find $n$.

My only approach is to make that graph, but I find difficulties to find that. I dont think hand-shake lemma could solve this.

2

There are 2 best solutions below

2
On

A has 10 vertices which each have degree 6, meaning there are 60 edges in the graph in total, as the graph is bipartite. Now the sum of degrees in B is $4*2+3*4+(n-17)*8 = 8n - 116$. Using the handshaking lemma $2*60 = (8n - 116)+60$ hence $n = 22$.

0
On

You can also go like this.

Since each vertex of $A$ has degree $10$, the number of edges of graph $G$ is $10\cdot6=60$. On the other hand, the number of edges coming from vertices of $B$ is $4\cdot2+3\cdot4+8x=60$. Hence $x=5$ and $n=22$.