Graph with 7 vertices and 11 edges and its vertices can be divided into two sets in such a way that no edge joins two vertices in the same set.

Question

Question: The graph has 7 vertices and 11 edges and its vertices can be divided into two sets in such a way that no edge joins two vertices in the same set.

How do I know if this graph exist or not. If yes how do i draw it out, if no why?

Answer 1

HINT: If the $7$ vertices are divided into two sets of size $a$ and $b$, then there are at most $a\cdot b$ edges between them. So then $a\cdot b\geq11$ and $a+b=7$. Now see if you can draw such a graph.

Answer 2

Note that this is a bipartite graph $G=(V,E)$. You can find a partition of $V$ into two subsets $V_1,V_2\subset V$, such that $u,w\in V_1\implies \{u,w\}\not\in E$ and similarly $u,w\in V_2\implies \{u,w\}\not\in E$. Now we see that $\sum_{v_i\in V_j}d(v_i)=11$ for $j=1,2$. This is impossible if $|V_1|=1,2$.

Therefore, without loss of generality, we may assume $|V_1|=3$. Let $V_1=\{v_1,v_2,v_3\}$ and $V_2=\{v_4,v_5,v_6,v_7\}$. Then let $G'=(V,E')=K_{3,4}$ and let $E=E'\setminus\{v_3,v_7\}$. Here $K_{n,m}$ denotes a complete bipartite graph with $V=V_1\cup V_2$, $V_1\cap V_2=\varnothing$, and $|V_1|=n$, $|V_2|=m$.