Conditions for a bipartite graph

Question

Is a 8 vertices graph with degree $3$ and $12$ edges a bipartite graph? For instance, $24$ is the sum of degree and it is twice the number of edges and theorem 1 it says any graph is bipartite if the sum of the degree of all vertices is equal to twice the number of edges. The problem is that when I give the partition some of the vertices are adjacent to each other and even if they are in the same set. Like $V1 = \{a,c,f,h\}$ and $V2 = \{b,d,e,g\}$ and $a$ is adjacent to $h$ or $e$ is adjacent to $d$. Does it matter if they are adjacent in the same set?

Answer 1

This graph can be both bipartite and unbipartite and the info you gave isn't enough to decide whether it is or it isn't. The only theorem about bipartite graphs based on their properties is that the graph $G$ is bipartite iff it doesn't have any odd cycles and clearly your graph can be of both types.
For a example of a bipartite graph of this type, draw four vertices $A_1,A_2,A_3,A_4$ in the first set and $B_1,B_2,B_3,B_4$ in the second set. Then connect $A_1$ to $B_2,B_3,B_4$ , connect $A_2$ to $B_1,B_3,B_4$ , etc. and the graph is bipartite. For the opposite, make a $C_4$ with $A_1,A_2,B_1,B_2$ and another $C_4$ with the other vertices and it will be unbipartite because it has several cycles of length 3.

Answer 2

The theorem I think you are talking about doesn't have anything to do with whether a graph is bipartite or not - its the handshaking lemma which just observes that the sum of the vertex degrees must count all the edges twice.

Graphs where every vertex has the same degree are called regular. If all the vertices have degree $k$ they are $k$-regular and in particular $3$-regular graphs are called cubic.

Typically, knowing the degree sequence of a graph (which gives the degree of every vertex) is not enough to establish whether or not it is bipartite - that usually requires knowing how the vertices are connected, since - to specifically answer a question there - the defining quality of a bipartite graph is that there are no connections between nodes in the same part.

Here's a couple of graphs that fit your description - one is bipartite, one is not. In the bipartite graph on the left, the red nodes are only ever connected to blue nodes and vice-versa. I've highlighted a cycle of length $5$ in the non-bipartite graph, since you never find odd-length cycles in bipartite graphs - it would be impossible to make the colouring described for the other graph.