To determine if following graphs are bipartite:
a) the graph on 7 vertices one for each day of week, where two days are adjacent exactly if they share a letter in their name (but the letter must not be "d","a" or "y")
b) the graph on 7 vertices one for each day of week, where two days are adjacent exactly if they do not share a letter in their name (but the letter must not be "d","a" or "y")
c) edge graph of a cube
d) edge graph of tetrahedron
My try:
I think I got c and d. c would be bipartite and d is not.
Need help in a and b (not able to figure out)
After you remove the letters d, a, and y and all repeated letters from the names of the weekdays, you have
$$\begin{array}{ll} 1&\text{Monday}&\text{mno}\\ 2&\text{Tuesday}&\text{estu}\\ 3&\text{Wednesday}&\text{ensw}\\ 4&\text{Thursday}&\text{hrstu}\\ 5&\text{Friday}&\text{fir}\\ 6&\text{Saturday}&\text{rstu}\\ 7&\text{Sunday}&\text{nsu} \end{array}$$
I’ll use the numbers in the first column as names of the $7$ vertices of the graphs (a) and (b). In graph (a) we have the following edges, with a shared letter in parentheses:
$$\begin{align*} &13(n),17(n),\\ &23(e),24(s),26(s),27(s),\\ &34(s),36(s),37(n),\\ &45(r),46(r),47(s)\\ &56(r),\\ &67(s) \end{align*}\tag{1}$$
Suppose that the graph is bipartite, with parts $V$ and $W$, and without loss of generality suppose that $1\in V$. The first line of $(1)$ shows that $3$ and $7$ must be in $W$, since there are edges between them and $1$. Since $7\in W$, and $7$ is joined by edges to $2,3,4$, and $6$, these four vertices must join $1$ in $V$. And we have an edge $56$, so with $6\in V$ we must have $5\in W$. That is, we must have
$$V=\{1,2,3,4,6\}\quad\text{and}\quad W=\{5,7\}\;.$$
Unfortunately, this doesn’t work, because we have an edge $23$ between two vertices in $V$. Thus, graph (a) is not bipartite.
Note that we didn’t actually need all of the information. It’s enough to see that we have edges $23,27$, and $37$, forming a triangle: a bipartite graph cannot contain a triangle.
Now that you’ve seen this, see if you can deal with graph (b) on your own.