Welcome, my dear students! Today we are going to learn a very beautiful and visual topic in Discrete Mathematics — Elements of Graph Theory. I know “graph” might make you think of bar charts or pie charts, but in mathematics, a graph is something completely different. It is a way to study connections between objects. So, let us start this journey together, step by step.
1. Definitions and Examples of a Graph
Imagine you are looking at a map of cities connected by roads. Each city is a point, and each road is a line connecting two cities. That is exactly what a graph is in mathematics!
Definition: A graph \(G\) is an ordered pair \(G = (V, E)\), where:
– \(V\) is a finite non-empty set of elements called vertices (or nodes or points).
– \(E\) is a set of edges (or lines), where each edge connects a pair of vertices.
If an edge connects vertex \(u\) and vertex \(v\), we write it as \(e = \{u, v\}\) or simply \(e = uv\).
Let me make this clearer with a picture. Look at this small graph:
v1
/ \
/ \
v2—–v3
\ /
\ /
v4
Here, \(V = \{v_1, v_2, v_3, v_4\}\) and \(E = \{v_1v_2, v_1v_3, v_2v_3, v_2v_4, v_3v_4\}\). We say this graph has 4 vertices and 5 edges.
Important Terms You Must Know
Adjacent vertices: Two vertices are adjacent if there is an edge between them. In our graph, \(v_1\) and \(v_2\) are adjacent. But \(v_1\) and \(v_4\) are NOT adjacent (no direct edge).
Incident edge: An edge is incident to a vertex if that vertex is one of its endpoints. Edge \(v_1v_2\) is incident to both \(v_1\) and \(v_2\).
Degree of a vertex: The degree of a vertex \(v\), written as \(\deg(v)\), is the number of edges incident to it. Let me count for our graph:
- \(\deg(v_1) = 2\) (edges: \(v_1v_2\) and \(v_1v_3\))
- \(\deg(v_2) = 3\) (edges: \(v_1v_2, v_2v_3, v_2v_4\))
- \(\deg(v_3) = 3\) (edges: \(v_1v_3, v_2v_3, v_3v_4\))
- \(\deg(v_4) = 2\) (edges: \(v_2v_4, v_3v_4\))
Loop: An edge that connects a vertex to itself, like \(vv\). A loop adds 2 to the degree of that vertex.
Multiple edges (Parallel edges): When two or more edges connect the same pair of vertices.
Simple graph: A graph with no loops and no multiple edges. Most exam problems deal with simple graphs.
Multigraph: A graph that allows multiple edges but no loops.
Pseudograph: A graph that allows both loops and multiple edges.
Important Exam Formula — The Handshaking Theorem:
The sum of the degrees of ALL vertices in a graph is always equal to twice the number of edges.
\[ \sum_{v \in V} \deg(v) = 2|E| \]
Why? Because each edge contributes 1 to the degree of each of its two endpoints. So each edge is counted exactly twice!
Key consequence: The sum of all degrees is always even. This means a graph can never have an odd number of odd-degree vertices.
Worked Example 1: Using the Handshaking Theorem
Problem: A graph has 5 vertices with degrees 1, 2, 3, 4, and \(d\). Find the possible values of \(d\).
Solution: By the Handshaking Theorem, the sum of degrees must be even and equal to \(2|E|\).
\[ 1 + 2 + 3 + 4 + d = 10 + d \]
Since \(10 + d\) must be even, \(d\) must be even. Also, in a simple graph with 5 vertices, the maximum degree is 4 (a vertex can connect to at most 4 other vertices). So \(d\) can be 0, 2, or 4.
Practice Question 1 (MCQ): A graph has 3 vertices with degrees 2, 3, and 5. Is this graph possible?
A) Yes
B) No, because the sum of degrees is odd
C) No, because a vertex cannot have degree 5
D) No, because of both B and C
Answer: D. The sum is \(2 + 3 + 5 = 10\), which is actually even. BUT in a simple graph with only 3 vertices, the maximum degree is 2 (each vertex can connect to at most 2 others). So a vertex with degree 5 is impossible. If we allow multiple edges, the sum must still be even — but degree 5 with only 2 other vertices would need many parallel edges. In standard exam problems assuming simple graphs, this is impossible.
Practice Question 2 (Fill in the Blank): A graph has 4 vertices, each with degree 3. The number of edges is ______.
Answer: 6. Sum of degrees \(= 3 + 3 + 3 + 3 = 12\). By Handshaking Theorem, \(2|E| = 12\), so \(|E| = 6\). This graph is the complete graph \(K_4\), which we will learn about soon.
Practice Question 3 (True/False): A simple graph with 4 vertices can have one vertex of degree 4.
Answer: False. In a simple graph with 4 vertices, each vertex can connect to at most 3 other vertices (no loops, no multiple edges). So the maximum degree is 3, not 4.
2. Matrix Representation of a Graph
Now, how do we represent a graph in a computer or in an exam on paper without drawing pictures? We use matrices! There are two main types: the adjacency matrix and the incidence matrix.
Adjacency Matrix
Definition: The adjacency matrix \(A\) of a graph \(G = (V, E)\) with \(n\) vertices is an \(n \times n\) matrix where:
\[ A_{ij} = \begin{cases} 1 & \text{if there is an edge between } v_i \text{ and } v_j \\ 0 & \text{otherwise} \end{cases} \]
Let me show you with an example. Consider this graph:
v1 — v2
| / |
| / |
| / |
v3 — v4
Edges: \(v_1v_2, v_1v_3, v_2v_3, v_2v_4, v_3v_4\)
The adjacency matrix (labeling vertices in order \(v_1, v_2, v_3, v_4\)):
| \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) |
|---|
| \(v_1\) | 0 | 1 | 1 | 0 |
| \(v_2\) | 1 | 0 | 1 | 1 |
| \(v_3\) | 1 | 1 | 0 | 1 |
| \(v_4\) | 0 | 1 | 1 | 0 |
Key Properties of the Adjacency Matrix (Remember for Exam!):
1. For a simple undirected graph, the adjacency matrix is always symmetric (\(A_{ij} = A_{ji}\)).
2. The diagonal entries are all 0 (no loops in a simple graph).
3. The degree of vertex \(v_i\) = sum of the entries in row \(i\) = sum of entries in column \(i\).
4. The number of edges = half the sum of ALL entries in the matrix (because each edge is counted twice).
Incidence Matrix
Definition: The incidence matrix \(M\) of a graph \(G = (V, E)\) with \(n\) vertices and \(m\) edges is an \(n \times m\) matrix where:
\[ M_{ij} = \begin{cases} 1 & \text{if vertex } v_i \text{ is incident to edge } e_j \\ 0 & \text{otherwise} \end{cases} \]
For the same graph with edges \(e_1 = v_1v_2, e_2 = v_1v_3, e_3 = v_2v_3, e_4 = v_2v_4, e_5 = v_3v_4\):
| \(e_1\) | \(e_2\) | \(e_3\) | \(e_4\) | \(e_5\) |
|---|
| \(v_1\) | 1 | 1 | 0 | 0 | 0 |
| \(v_2\) | 1 | 0 | 1 | 1 | 0 |
| \(v_3\) | 0 | 1 | 1 | 0 | 1 |
| \(v_4\) | 0 | 0 | 0 | 1 | 1 |
Notice: each column of the incidence matrix has exactly two 1s (because each edge connects exactly two vertices).
Worked Example 2: Finding Degree from Adjacency Matrix
Problem: The adjacency matrix of a graph with 4 vertices is:
\[ A = \begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 \end{pmatrix} \]
Find the degree of each vertex and the total number of edges.
Solution: Sum each row to get the degree:
– \(\deg(v_1) = 0 + 1 + 0 + 1 = 2\)
– \(\deg(v_2) = 1 + 0 + 1 + 1 = 3\)
– \(\deg(v_3) = 0 + 1 + 0 + 0 = 1\)
– \(\deg(v_4) = 1 + 1 + 0 + 0 = 2\)
Total sum of degrees \(= 2 + 3 + 1 + 2 = 8\). So number of edges \(= 8/2 = 4\).
Practice Question 4 (MCQ): The adjacency matrix of a simple undirected graph is always:
A) An identity matrix
B) Symmetric with all diagonal entries zero
C) Asymmetric
D) A diagonal matrix
Answer: B. A simple undirected graph has no loops (diagonal entries are 0) and edges are undirected (so if \(v_i\) is adjacent to \(v_j\), then \(v_j\) is adjacent to \(v_i\), making the matrix symmetric). This is a fundamental property you must remember.
Practice Question 5 (Short Answer): In the incidence matrix of a simple graph, why does each column have exactly two 1s?
Answer: Each column represents an edge. In a simple graph, each edge connects exactly two vertices (no loops allowed). Therefore, exactly two vertices are incident to each edge, giving exactly two 1s per column. If loops were allowed, a loop column would have only one 1 (or a 2 depending on convention, but in the standard definition it is one 1).
3. Isomorphic Graphs
Now, here is a question I like to ask in class: “If I draw a graph on paper and you draw the SAME graph but move the vertices around, are they the same graph?” The answer is yes! And that idea leads us to graph isomorphism.
Definition: Two graphs \(G_1 = (V_1, E_1)\) and \(G_2 = (V_2, E_2)\) are isomorphic if there exists a one-to-one correspondence (bijection) \(f: V_1 \to V_2\) such that:
\[ \{u, v\} \in E_1 \iff \{f(u), f(v)\} \in E_2 \]
In simple words: you can relabel the vertices of \(G_1\) to get exactly \(G_2\).
Think of it like this: two graphs are isomorphic if they have the same structure, just with different names or positions for the vertices.
Graph G1: Graph G2:
a w
/ \ / \
b c x y
\ / \ /
d zSame structure! Just renamed:
a->w, b->x, c->y, d->z
How to Check for Isomorphism in Exams
You cannot just look at the picture and say “they look different.” You need to check invariants — properties that must be the same if two graphs are isomorphic:
Necessary Conditions for Isomorphism (if ANY of these fail, the graphs are NOT isomorphic):
1.
Same number of vertices
2.
Same number of edges
3.
Same degree sequence (the list of all degrees, sorted)
4.
Same number of cycles of each length (if you can easily count them)
Important: Even if ALL these conditions match, the graphs MAY STILL not be isomorphic. These are necessary but NOT sufficient conditions. To prove isomorphism, you must actually find the mapping.
Worked Example 3: Checking Isomorphism
Problem: Are these two graphs isomorphic?
Graph G1: Graph G2:
a (deg 2) p (deg 2)
/ \ / \
b c (deg 3) q r (deg 2)
\ / \ /
d (deg 3) s (deg 3)Edges of G1: Edges of G2:
ab, ac, bc, bd, cd pq, pr, qs, rs, ps
Step 1: Same number of vertices? Yes (4 each).
Step 2: Same number of edges? Yes (5 each).
Step 3: Same degree sequence?
– \(G_1\): degrees are 2, 2, 3, 3 → sorted: (3, 3, 2, 2)
– \(G_2\): degrees are 2, 2, 2, 3 → sorted: (3, 2, 2, 2)
Different degree sequences! So the graphs are NOT isomorphic. We did not even need to try to find a mapping.
Practice Question 6 (MCQ): Two graphs \(G_1\) and \(G_2\) have the same number of vertices and the same number of edges. Can we conclude they are isomorphic?
A) Yes, always
B) No, never
C) Not necessarily; we need more checks
D) Only if they have the same degree sequence
Answer: C. Having the same number of vertices and edges is necessary but far from sufficient. Many non-isomorphic graphs share the same vertex and edge counts. Even matching degree sequences is not always enough (though it is a stronger check). The only way to PROVE isomorphism is to find a valid vertex mapping.
Practice Question 7 (True/False): If two graphs have different degree sequences, they must be non-isomorphic.
Answer: True. The degree sequence is an invariant under isomorphism. If \(f\) is an isomorphism, then \(\deg(f(v)) = \deg(v)\) for every vertex. So isomorphic graphs MUST have the same degree sequence. If they do not, they cannot be isomorphic.
4. Path and Connectivity of a Graph
Now let us talk about how to travel within a graph. Can you get from one vertex to another? This is the idea of connectivity.
Definition: A walk in a graph is a sequence of vertices and edges: \(v_0, e_1, v_1, e_2, v_2, \ldots, e_k, v_k\) where each edge \(e_i\) connects \(v_{i-1}\) and \(v_i\). The length of the walk is the number of edges, \(k\).
There are special types of walks:
- Trail: A walk where no edge is repeated (but vertices may repeat).
- Path: A walk where no vertex is repeated (which also means no edge is repeated). This is the most important one for exams!
- Closed walk: A walk that starts and ends at the same vertex (\(v_0 = v_k\)).
- Circuit: A closed trail (starts and ends at same vertex, no repeated edges).
- Cycle: A closed path (starts and ends at same vertex, no repeated vertices except start=end, length at least 3).
Easy Way to Remember:
– Walk = anything goes (can repeat vertices and edges)
– Trail = edges cannot repeat
– Path = vertices cannot repeat (strongest condition)
– Add “Closed” = starts and ends at the same vertex
– Cycle = closed path (at least 3 vertices)
Connectivity
Definition: A graph \(G\) is connected if there is a path between every pair of vertices. If a graph is not connected, it is disconnected and consists of two or more connected components.
Connected Graph: Disconnected Graph (2 components):a—b—c a—b d—e
| | |
d c fOne piece Two separate pieces
Connected component: A maximal connected subgraph. A disconnected graph breaks into several connected components.
Worked Example 4: Identifying Paths and Cycles
Problem: In the graph below, identify whether each sequence is a walk, trail, path, cycle, or none.
a—b
| /|
| / |
|/ |
c—dEdges: ab, ac, bc, bd, cd
Sequences:
1. \(a, b, c, a\) — This is a closed walk. Vertices: \(a, b, c, a\). No vertex repeats except start=end. It has 3 edges. This is a cycle of length 3 (a triangle).
2. \(a, b, d, c, a\) — Vertices: \(a, b, d, c, a\). No repeats except start=end. 4 edges. This is a cycle of length 4.
3. \(a, b, c, b, d\) — Vertex \(b\) repeats. Edges used: \(ab, bc, cb, bd\). Edge \(bc\) is used twice! This is a walk (repeats both vertex and edge), but NOT a trail.
4. \(a, c, d, b\) — All vertices different. This is a path of length 3.
Exam Tip: When asked “find a path from \(u\) to \(v\),” make sure NO vertex repeats. When asked “find a trail,” make sure NO edge repeats (vertices can repeat). Students often confuse these two!
Practice Question 8 (MCQ): In a simple graph with \(n\) vertices, what is the maximum possible length of a path?
A) \(n\)
B) \(n-1\)
C) \(n+1\)
D) \(2n\)
Answer: B. A path has no repeated vertices. With \(n\) vertices, the longest path visits each vertex exactly once, using \(n-1\) edges. So the maximum length is \(n-1\). A path of length \(n\) would need \(n+1\) vertices, which is impossible in an \(n\)-vertex graph.
Practice Question 9 (True/False): Every trail is also a path.
Answer: False. A trail does not repeat edges but MAY repeat vertices. A path does not repeat vertices. So a trail that repeats a vertex (like \(a-b-c-b-d\)) is a trail but NOT a path. Every path IS a trail, but not every trail is a path.
Practice Question 10 (Short Answer): A graph has 6 vertices and 3 connected components. What is the minimum number of edges it can have?
Answer: 3. Each connected component must have at least 1 vertex. With 6 vertices and 3 components, one possible split is components of sizes 2, 2, and 2 (or 4, 1, 1, etc.). The minimum edges occur when each component is a tree (or just a single vertex). A tree on \(k\) vertices has \(k-1\) edges. If we split as 4, 1, 1: edges = 3 + 0 + 0 = 3. If we split as 2, 2, 2: edges = 1 + 1 + 1 = 3. So the minimum is 3 edges.
5. Complete, Regular, and Bipartite Graphs
Now let me introduce you to some very important special types of graphs. These appear in exams very frequently!
Complete Graph \(K_n\)
Definition: A complete graph \(K_n\) is a simple graph with \(n\) vertices where every pair of distinct vertices is connected by an edge.
Number of edges in \(K_n\): \(\displaystyle |E| = \frac{n(n-1)}{2} = \binom{n}{2}\)
Degree of each vertex in \(K_n\): \(n – 1\)
K3 (Triangle): K4: K5:a—b a a
\ / / \ / \
c b—c b—c
\ / |\ /|
d d—e
\ /
f
(6 edges) (10 edges)
Regular Graph
Definition: A graph is \(k\)-regular if every vertex has the same degree \(k\).
Important fact: If a \(k\)-regular graph has \(n\) vertices, then by the Handshaking Theorem:
\[ n \cdot k = 2|E| \implies |E| = \frac{nk}{2} \]
This means \(nk\) must be even.
Example: \(K_n\) is \((n-1)\)-regular. The Petersen graph is 3-regular.
Exam Tip: If a question says “a 3-regular graph has 7 vertices, how many edges?” — first check: \(nk = 7 \times 3 = 21\), which is ODD. But \(2|E|\) must be even. So no such graph exists! Always check this condition first.
Bipartite Graph
Definition: A graph \(G = (V, E)\) is bipartite if we can divide the vertex set \(V\) into two disjoint sets \(V_1\) and \(V_2\) (\(V_1 \cup V_2 = V\) and \(V_1 \cap V_2 = \emptyset\)) such that every edge connects a vertex in \(V_1\) to a vertex in \(V_2\).
No edge connects two vertices within the same set.
Bipartite Graph: NOT Bipartite:V1 = {a, b} x—y
V2 = {c, d, e} |\ /|
| x |
a—c |/ \|
| | w—z
b—d—eAll edges go from Edge xy and edge wz
V1 to V2 only are within same “side”
Complete Bipartite Graph \(K_{m,n}\): A bipartite graph where \(|V_1| = m\), \(|V_2| = n\), and every vertex in \(V_1\) is connected to every vertex in \(V_2\).
Number of edges in \(K_{m,n}\): \(m \times n\)
Degrees: All vertices in \(V_1\) have degree \(n\); all vertices in \(V_2\) have degree \(m\).
Theorem for Exam — How to Check if a Graph is Bipartite:
A graph is bipartite if and only if it contains no odd-length cycles.
This is a very powerful theorem! If you can find any cycle of odd length (3, 5, 7, …), the graph is NOT bipartite.
Worked Example 5: Identifying Special Graphs
Problem: Is \(K_3\) bipartite?
Solution: \(K_3\) is a triangle (3 vertices, each connected to the other two). It contains a cycle of length 3 (odd!). Therefore, by the theorem, \(K_3\) is NOT bipartite.
In fact, \(K_n\) is bipartite only when \(n \leq 2\). \(K_2\) is bipartite (put each vertex in a different set). \(K_1\) is trivially bipartite.
Worked Example 6: Complete Bipartite Graph
Problem: How many edges does \(K_{3,4}\) have? What are the degrees?
Solution: \(K_{3,4}\) has one part with 3 vertices and another with 4 vertices. Every vertex in the first part connects to every vertex in the second part.
Number of edges \(= 3 \times 4 = 12\).
Degrees: vertices in the part of size 3 have degree 4; vertices in the part of size 4 have degree 3.
Practice Question 11 (MCQ): Which of the following is bipartite?
A) \(K_3\)
B) \(K_4\)
C) \(K_{2,3}\)
D) A graph containing a triangle
Answer: C. \(K_{2,3}\) is a complete bipartite graph by definition — it is bipartite with parts of size 2 and 3. Options A and B contain triangles (odd cycles), so they are not bipartite. Option D explicitly states it has a triangle (odd cycle), so it is not bipartite.
Practice Question 12 (Fill in the Blank): A 5-regular graph has 8 vertices. The number of edges is ______.
Answer: 20. Using \(|E| = \frac{nk}{2} = \frac{8 \times 5}{2} = 20\). Note that \(nk = 40\) is even, so such a graph could exist.
Practice Question 13 (True/False): Every regular graph is also a complete graph.
Answer: False. A regular graph only requires that all vertices have the same degree. A complete graph requires that every pair of vertices is connected. For example, a cycle graph \(C_4\) (a square) is 2-regular but NOT complete (not all pairs are connected). Regular is a weaker condition than complete.
6. Eulerian and Hamiltonian Graphs
Now we reach two of the most famous topics in graph theory. Students often confuse these two, so let me be very clear about the difference.
EULERIAN vs HAMILTONIAN – Know the Difference!EULERIAN: HAMILTONIAN:
“Visit every EDGE once” “Visit every VERTEX once”Think: Mail carrier Think: Tourist visiting
delivering mail on all cities exactly once
every road exactly once
Eulerian Graphs
Definition: An Eulerian circuit is a closed trail that uses every edge exactly once.
An Eulerian path (or Euler trail) is a trail that uses every edge exactly once but does NOT need to be closed (start and end may differ).
A graph is Eulerian if it contains an Eulerian circuit.
Euler’s Theorem (Must Memorize for Exam!):
A connected graph has an Eulerian circuit if and only if every vertex has even degree.
A connected graph has an Eulerian path (but NOT a circuit) if and only if it has exactly two vertices of odd degree. (The path must start at one odd-degree vertex and end at the other.)
Important: If a connected graph has more than two odd-degree vertices, it has NEITHER an Eulerian circuit NOR an Eulerian path.
Worked Example 7: Eulerian Circuit Check
Problem: Does the following graph have an Eulerian circuit, an Eulerian path, or neither?
a—b
| |
c—d
| |
e—f
Solution: Count the degree of each vertex:
\(\deg(a) = 2, \deg(b) = 2, \deg(c) = 2, \deg(d) = 2, \deg(e) = 2, \deg(f) = 2\)
ALL vertices have even degree. The graph is connected. So it has an Eulerian circuit.
One possible Eulerian circuit: \(a \to b \to d \to f \to e \to c \to a\)
Worked Example 8: Eulerian Path Only
Problem: Does the following graph have an Eulerian circuit, path, or neither?
a—b—c
|
d
Solution: Degrees: \(\deg(a) = 1, \deg(b) = 3, \deg(c) = 1, \deg(d) = 1\)
Three vertices have odd degree (\(a, c, d\)). Since there are more than two odd-degree vertices, the graph has neither an Eulerian circuit nor an Eulerian path.
Hamiltonian Graphs
Definition: A Hamiltonian cycle is a cycle that visits every vertex exactly once (and returns to the starting vertex).
A Hamiltonian path visits every vertex exactly once but does not return to the start.
A graph is Hamiltonian if it contains a Hamiltonian cycle.
Important Difference from Euler: There is NO simple degree condition for Hamiltonian graphs like there is for Eulerian graphs. Determining whether a graph is Hamiltonian is generally much harder. We only have sufficient conditions (rules that guarantee a Hamiltonian cycle exists) but no simple “if and only if” condition.
Dirac’s Theorem (Sufficient Condition):
If \(G\) is a simple graph with \(n \geq 3\) vertices and every vertex has degree at least \(n/2\), then \(G\) is Hamiltonian.
Ore’s Theorem (More General Sufficient Condition):
If \(G\) is a simple graph with \(n \geq 3\) vertices and for every pair of non-adjacent vertices \(u\) and \(v\): \(\deg(u) + \deg(v) \geq n\), then \(G\) is Hamiltonian.
Exam Tip: Dirac’s and Ore’s theorems are sufficient conditions, NOT necessary. A graph can be Hamiltonian even if it does NOT satisfy these theorems. For example, a cycle graph \(C_n\) is Hamiltonian but may not satisfy Dirac’s condition. These theorems help you prove a graph IS Hamiltonian, but they cannot prove it is NOT.
Worked Example 9: Checking Hamiltonian Using Dirac’s Theorem
Problem: Is \(K_5\) Hamiltonian?
Solution: \(K_5\) has \(n = 5\) vertices, each with degree \(n – 1 = 4\).
Dirac’s condition: every vertex has degree \(\geq n/2 = 5/2 = 2.5\). Since \(4 \geq 2.5\), the condition is satisfied.
Therefore, \(K_5\) is Hamiltonian. (In fact, every \(K_n\) with \(n \geq 3\) is Hamiltonian.)
Worked Example 10: When Dirac’s Theorem Does Not Apply
Problem: Is the cycle graph \(C_5\) (a pentagon) Hamiltonian?
Solution: \(C_5\) has 5 vertices, each with degree 2. Dirac’s condition requires degree \(\geq 2.5\). Since \(2 < 2.5\), Dirac's theorem does NOT apply.
But \(C_5\) IS Hamiltonian — just go around the cycle! The cycle itself is a Hamiltonian cycle.
This shows that Dirac’s theorem is sufficient but NOT necessary.
Practice Question 14 (MCQ): A connected graph has vertices with degrees 2, 2, 4, 4, 4. Which of the following is true?
A) It has an Eulerian circuit
B) It has an Eulerian path but not a circuit
C) It has neither an Eulerian circuit nor path
D) It cannot be determined from degree information alone
Answer: A. All vertices have even degrees (2, 2, 4, 4, 4). For a connected graph, this means it has an Eulerian circuit. The graph is connected (given), and all degrees are even — this is the “if and only if” condition for Eulerian circuits.
Practice Question 15 (MCQ): A connected graph has exactly two vertices of odd degree. It has:
A) An Eulerian circuit
B) An Eulerian path but not a circuit
C) Neither an Eulerian circuit nor path
D) A Hamiltonian cycle
Answer: B. By Euler’s theorem, a connected graph with exactly two odd-degree vertices has an Eulerian path (starting at one odd vertex and ending at the other) but NOT an Eulerian circuit (which requires all even degrees). Option D is unrelated — we cannot determine Hamiltonian property from just this information.
Practice Question 16 (True/False): If a graph satisfies Dirac’s condition, it must be Hamiltonian. If a graph does NOT satisfy Dirac’s condition, it must NOT be Hamiltonian.
Answer: False (the second part is wrong). Dirac’s theorem says: IF every vertex has degree \(\geq n/2\), THEN the graph IS Hamiltonian. But the converse is NOT true — a graph CAN be Hamiltonian without satisfying Dirac’s condition (like \(C_5\)). The first part of the statement is correct; the second part is false.
Practice Question 17 (Short Answer): A connected graph has vertices with degrees 1, 2, 2, 3. Does it have an Eulerian circuit? An Eulerian path?
Answer: It has two odd-degree vertices (1 and 3) and two even-degree vertices (2 and 2). Since it is connected and has exactly two odd-degree vertices, it has an Eulerian path (but NOT an Eulerian circuit). The path must start at the vertex with degree 1 and end at the vertex with degree 3 (or vice versa).
7. Quick Comparison: Eulerian vs Hamiltonian
| Property | Eulerian | Hamiltonian |
|---|
| Visits every… | Edge exactly once | Vertex exactly once |
| Circuit condition | All degrees even (if and only if) | No simple if-and-only-if condition |
| Path condition | Exactly 2 odd-degree vertices | Even harder to determine |
| Difficulty to check | Easy (just check degrees!) | Hard (NP-complete problem) |
| Named after | Leonhard Euler | William Rowan Hamilton |
Final Exam Tips:
1. For Eulerian questions: always count the degrees first. This tells you everything.
2. For Hamiltonian questions: try to find a cycle manually first. If you cannot, try using Dirac’s or Ore’s theorem to PROVE it exists.
3. Remember: “Euler = Edges, Hamilton = Hover (visit all vertices).”
4. For bipartite graphs: check for odd cycles.
5. For isomorphism: check degree sequence FIRST — it is the quickest way to rule out isomorphism.
Challenge Conceptual Exam Questions
These questions are designed to test your deep understanding. Take your time and think carefully!
Multiple Choice Questions
Q1. A simple graph has 6 vertices. What is the maximum number of edges it can have?
A) 12
B) 15
C) 18
D) 30
Answer: B. The maximum number of edges in a simple graph with \(n\) vertices is \(\binom{n}{2} = \frac{n(n-1)}{2}\). Here: \(\frac{6 \times 5}{2} = 15\). This is the complete graph \(K_6\). Option C would be if each vertex had degree 6, but that is impossible (max degree is 5).
Q2. The adjacency matrix of a graph has all diagonal entries equal to 0 and is symmetric. What can we conclude?
A) The graph is a complete graph
B) The graph is a simple undirected graph
C) The graph is a tree
D) The graph is bipartite
Answer: B. Diagonal entries being 0 means no loops. Symmetry means edges are undirected (\(A_{ij} = A_{ji}\)). These are exactly the properties of a simple undirected graph’s adjacency matrix. We cannot conclude it is complete (that would need all off-diagonal entries to be 1), a tree (that depends on connectivity and edge count), or bipartite (that depends on cycle structure).
Q3. Which of the following graphs is definitely NOT bipartite?
A) A tree
B) \(K_{2,5}\)
C) A graph with a cycle of length 4
D) A graph with a cycle of length 5
Answer: D. A graph is bipartite if and only if it has no odd-length cycles. A cycle of length 5 is odd, so any graph containing it is NOT bipartite. Trees (option A) are always bipartite (they have no cycles at all). \(K_{2,5}\) (option B) is bipartite by definition. A cycle of length 4 (option C) is even, so it is compatible with bipartiteness.
Q4. A graph is 3-regular and has 10 vertices. How many edges does it have?
A) 15
B) 30
C) 20
D) Such a graph cannot exist
Answer: A. Using the formula \(|E| = \frac{nk}{2} = \frac{10 \times 3}{2} = 15\). Since \(nk = 30\) is even, such a graph can exist. For example, the Petersen graph is exactly 3-regular with 10 vertices and 15 edges!
Q5. If a connected graph has an Eulerian circuit, which statement must be true?
A) It also has a Hamiltonian cycle
B) Every vertex has even degree
C) It is a complete graph
D) It is bipartite
Answer: B. By Euler’s theorem, a connected graph has an Eulerian circuit if and only if every vertex has even degree. Option A is false — consider a rectangle (4 vertices, 4 edges, all degree 2): it has an Eulerian circuit but no Hamiltonian cycle (you cannot visit all 4 vertices and return without repeating a vertex… actually wait, a rectangle IS a cycle of length 4, which IS Hamiltonian. Better example: two triangles sharing one vertex — all degrees even (2,2,2,4), Eulerian circuit exists, but no Hamiltonian cycle because the shared vertex would need to be visited twice). Option C and D are unrelated.
True / False Questions
Q6. If two graphs have the same adjacency matrix, they must be isomorphic.
Answer: True (with a caveat about labeling). If two graphs have the EXACT same adjacency matrix (same size, same entries in the same positions), it means they have the same vertices with the same edges — they are identical graphs, which is a special case of isomorphism. However, the more subtle point is: two isomorphic graphs can have DIFFERENT adjacency matrices if the vertices are labeled differently. But if the matrices are literally the same, the graphs are the same.
Q7. Every Hamiltonian graph is also Eulerian.
Answer: False. These are completely different concepts. Consider a simple path graph with 3 vertices: \(a-b-c\). This has a Hamiltonian path (visits all vertices) but no Eulerian path (it has two odd-degree vertices, which actually means it DOES have an Eulerian path… let me use a better example). Consider the complete graph \(K_4\): it is Hamiltonian (has a Hamiltonian cycle), and it is also Eulerian (all degrees are 3… wait, 3 is odd, so it is NOT Eulerian). Actually, \(K_4\) has all vertices with degree 3 (odd), so it has an Eulerian path but NOT an Eulerian circuit. Better example: a star graph \(K_{1,3}\) is Hamiltonian… no it is not. Let me think clearly: the cycle graph \(C_5\) is Hamiltonian (the cycle itself) but all degrees are 2 (even), so it IS Eulerian. For a clear counterexample: the Petersen graph is Hamiltonian but NOT Eulerian (all degrees are 3, which is odd, and there are 10 odd-degree vertices).
Q8. A bipartite graph cannot contain a triangle.
Answer: True. A triangle is a cycle of length 3 (odd). A graph is bipartite if and only if it contains no odd cycles. Therefore, a bipartite graph cannot contain a triangle. This is a very useful fact for exams.
Q9. If a graph is disconnected, it cannot have an Eulerian circuit.
Answer: True. An Eulerian circuit must traverse ALL edges and return to the starting point. If the graph is disconnected, there is no way to reach edges in one component from another component. So a disconnected graph cannot have an Eulerian circuit. (It could have Eulerian circuits within each component separately, but not for the whole graph.)
Fill in the Blank Questions
Q10. The number of edges in \(K_{7}\) is ______.
Answer: 21. Using \(\binom{7}{2} = \frac{7 \times 6}{2} = 21\). Each of the 7 vertices connects to all 6 others, giving \(7 \times 6 = 42\) “endpoint connections,” and each edge is counted twice, so \(42/2 = 21\).
Q11. A connected graph has 4 vertices with degrees 1, 2, 2, 3. It has an ______ (Eulerian circuit / Eulerian path / neither) because it has ______ odd-degree vertex(es).
Answer: Eulerian path, two. The graph has exactly two odd-degree vertices (1 and 3). By Euler’s theorem, a connected graph with exactly two odd-degree vertices has an Eulerian path (but not a circuit). The path starts at one odd vertex and ends at the other.
Q12. The sum of all entries in the adjacency matrix of a simple graph with 6 edges is ______.
Answer: 12. Each edge contributes two 1s to the adjacency matrix (one at position \((i,j)\) and one at \((j,i)\) due to symmetry). So 6 edges contribute \(6 \times 2 = 12\) ones. The total sum of all entries is 12.
Short Answer / Workout Questions
Q13. A graph has 5 vertices with degrees 1, 1, 2, 2, 2. Is this graph connected? Explain your reasoning.
Answer: No, this graph is not connected. Here is why: the two vertices with degree 1 are “endpoints” — each is connected to only one other vertex. With degrees 1, 1, 2, 2, 2, we can think of the structure. The maximum number of edges is \(5/2 \times 2 = 5\)… actually, let me use a direct argument. The total number of edges is \((1+1+2+2+2)/2 = 4\). A connected graph with 5 vertices needs at least \(5-1 = 4\) edges (a tree). So 4 edges is the minimum for connectivity. However, with two degree-1 vertices, consider: if the graph were a tree with 5 vertices, it would have exactly 4 edges and would be connected. A tree with two degree-1 vertices IS possible (like a path of length 4: \(v_1-v_2-v_3-v_4-v_5\), degrees 1,2,2,2,1). So actually, this graph COULD be connected!
Correction: The degree sequence 1,1,2,2,2 is consistent with a path graph \(P_5\), which IS connected. We cannot determine from the degree sequence alone whether the graph is connected or not. The answer depends on the actual edge structure, not just the degrees.
Q14. Use Ore’s theorem to determine whether the following graph is Hamiltonian: a graph with 5 vertices where every pair of non-adjacent vertices has degree sum at least 5. One vertex has degree 2, two vertices have degree 3, and two vertices have degree 4.
Answer: Let us check Ore’s condition: for every pair of non-adjacent vertices \(u, v\), we need \(\deg(u) + \deg(v) \geq n = 5\).
The smallest possible degree sum for any pair is \(2 + 3 = 5\) (if the degree-2 vertex is non-adjacent to a degree-3 vertex). This equals 5, which satisfies the condition \(\geq 5\).
All other pairs have higher sums: \(2+4=6\), \(3+3=6\), \(3+4=7\), \(4+4=8\). All \(\geq 5\).
Since the graph is simple with \(n = 5 \geq 3\) and Ore’s condition is satisfied for all non-adjacent pairs, the graph IS Hamiltonian by Ore’s theorem.
Q15. Two graphs \(G_1\) and \(G_2\) both have 6 vertices and 9 edges. \(G_1\) has degree sequence (3, 3, 3, 3, 3, 3) and \(G_2\) has degree sequence (5, 3, 3, 2, 2, 1). Are they isomorphic? Explain.
Answer: No, they are NOT isomorphic. The degree sequences are different: (3,3,3,3,3,3) versus (5,3,3,2,2,1). Since isomorphic graphs must have the same degree sequence, these two graphs cannot be isomorphic. We did not need to look at anything else — the degree sequence alone rules out isomorphism.
Note: \(G_1\) is a 3-regular graph on 6 vertices (like the utility graph, which is actually \(K_{3,3}\)). \(G_2\) has a vertex of degree 5, which in a 6-vertex simple graph means that vertex is connected to ALL other vertices.
Q16. Draw (describe) a graph that has an Eulerian circuit but is NOT Hamiltonian. Verify both properties.
Answer: Consider the graph consisting of two triangles sharing exactly one vertex:
a
/ \
b—c
\ /
d
/ \
e—f
Vertices: \(a, b, c, d, e, f\). Edges: \(ab, ac, bc, cd, de, df, ef\).
Eulerian circuit check: Degrees: \(\deg(a)=2, \deg(b)=2, \deg(c)=2, \deg(d)=2, \deg(e)=2, \deg(f)=2\). All even, graph is connected. So it HAS an Eulerian circuit (e.g., \(a-b-c-d-e-f-d-c-a\)).
Hamiltonian check: To visit all 6 vertices in a cycle, we must pass through vertex \(d\) (the shared vertex) twice — once to enter the second triangle and once to leave. But a cycle cannot visit any vertex twice. Therefore, there is NO Hamiltonian cycle.
This confirms the graph is Eulerian but NOT Hamiltonian.
Q17. Write the incidence matrix of \(K_{2,3}\) with vertex set \(V_1 = \{a, b\}\) and \(V_2 = \{p, q, r\}\). How many 1s are there in total, and why?
Answer: \(K_{2,3}\) has edges: \(ap, aq, ar, bp, bq, br\) — that is 6 edges.
The incidence matrix is a \(5 \times 6\) matrix:
| \(ap\) | \(aq\) | \(ar\) | \(bp\) | \(bq\) | \(br\) |
|---|
| \(a\) | 1 | 1 | 1 | 0 | 0 | 0 |
| \(b\) | 0 | 0 | 0 | 1 | 1 | 1 |
| \(p\) | 1 | 0 | 0 | 1 | 0 | 0 |
| \(q\) | 0 | 1 | 0 | 0 | 1 | 0 |
| \(r\) | 0 | 0 | 1 | 0 | 0 | 1 |
Total number of 1s = 12. This is because each of the 6 edges contributes exactly two 1s (one for each endpoint), so \(6 \times 2 = 12\). In general, for any simple graph, the incidence matrix has exactly \(2|E|\) ones.