Exercise 237Combinatorics › Graph theoryHigh schoolAdded 3 Nov 2026

Basic graph terminology

#graph#vertices#edges#degree

Statement

Let $G$ be a simple graph with vertices $V=\{1,2,3,4,5\}$ and edges $E=\{\{1,2\},\{2,3\},\{3,4\},\{4,5\},\{5,1\},\{1,3\}\}$ .

Give the order and size of $G$ .
Compute the degree of each vertex.
Is $G$ connected? Is it bipartite?

Hint

Order = number of vertices; size = number of edges. A graph is bipartite iff it has no odd cycle.

Show solutionHide solution

Solution

1. Order $|V|=5$ , size $|E|=6$ .

2. Degrees: $\deg(1)=3$ (neighbors $2,5,3$ ), $\deg(2)=2$ ( $1,3$ ), $\deg(3)=3$ ( $2,4,1$ ), $\deg(4)=2$ ( $3,5$ ), $\deg(5)=2$ ( $4,1$ ). Sum $=12=2\cdot6$ . ✓

3. Connected: yes (the cycle $1$ - $2$ - $3$ - $4$ - $5$ - $1$ links all). Bipartite: no, since the triangle $1$ - $2$ - $3$ - $1$ is an odd cycle.

Conclusion. Order $5$ , size $6$ ; connected; not bipartite.

Basic graph terminology

Statement

Solution

More problems in Graph theory