Graph-Theory
Pages in this section
- Bipartite graphLast edited: 2026-02-05Bipartite graph
A graph (directed graph or undirected graph ) $G = (V,E)$ is bipartite if you can partition the vertex set $V = V_1 \cup V_2$ such that for all $(u,v) \in E$ we have $u \in V_1$ and $v \in V_2$ or vice versa.
- Clique (graph)
Last edited: 2026-02-05Clique (graph)In an undirected graph $G = (V,E)$ a set of vertices $C \subset V$ is a clique if the induced subgraph on $C$ is the complete graph on $C$. (i.e. $\{(c,c') \vert \ c, c' \in C \text{ with } c \neq c'\} \subset E$.)
- Clique of a given size problem
Last edited: 2026-02-05# Statement
Clique of a given size problemGiven an undirected graph $G = (V,E)$ and a positive integer $g > 0$. Does there exist a clique of size at least $g$ if so what is it?
- Clique of a given size problem is in NP
Last edited: 2026-01-28# Statement
LemmaClique of a given size problem is in NP .
- Cliques in G are independent sets in the complement
Last edited: 2025-12-05# Statement
LemmaFor an undirected graph $G = (V,E)$ and $S \subset V$ we have the following equivalence: $S$ is a clique in $G$ if and only if $S$ is an independent set in $G^C$ the complement graph .
- Complement graph
Last edited: 2026-02-05Complement graphGiven an undirected graph or directed graph $G = (V,E)$. We define the complement graph
- Complete graph
Last edited: 2026-02-05Complete graphThe complete graph on $S$ is the undirected graph $(S, \{(s,s') \vert \ s, s' \in S \mbox{ with } s \not = s'\})$. (i.e. it is the graph with vertices $S$ and every possible edge between them excluding self-connected edges.)
- Connected (graph)
Last edited: 2023-11-11A graph $G = (V, E)$ is considered connected if for all vertices $x,y \in V$ there exists a path $\{v_i\}_{i=1}^k$ such that $v_1 = x$ and $v_k = y$.
- Connected components (graph)
Last edited: 2026-01-28Connected componentsIn a graph a connected component is a maximal connected subgraph $G'$ of $G$.
- Cycle (graph)
Last edited: 2023-11-11A cycle in a graph is path $\{e_i = (x_i, y_i)\}_{i=1}^{k}$ such that $x_1 = y_k$ and $e_i = e_j \Rightarrow i = j$.
Visual representationLets use our simple graph below
In this graph we have a cycle using the vertices $\{1,2,3\}$.- Degree (graph)
Last edited: 2023-11-11In a graph the degree of vertex is the number of ends of edges that are incidence to the vertex. This is denoted $\mbox{deg}(v)$ for some $v \in V$.
In a graph with no loops this is the same as the number of edges that are incident to the vertex. However, for evert loop in the graph on that vertex we have a contribution of 2 towards the vertex.
- Forest (graph)
Last edited: 2026-01-28ForestA graph is a forest if each of its connected components is a tree .
- Graph
Last edited: 2025-12-05GraphA simple undirected graph is a tuple of $V$, the vertex set, and $E \subset V \times V$, an edge set. This is normally referred to as $G = (V, E)$. As this is undirected, an edge $e = (x,y)$ is the same as the edge $e = (y,x)$, so if we define an equivalence relation $(x,y) \sim (y,x)$ for all $x,y \in V$, then it is fairer to say $E \subset V \times V / \sim$.
- Independent set (graph)
Last edited: 2026-02-05Independent set (graph)In a graph $G = (V,E)$ a subset $I \subset V$ is an independent set if the induced subgraph on $I$ has no edges. (i.e. for all $(u,v) \in E$ either $u \not \in I$ or $v \not \in I$.)
- Induced subgraph
Last edited: 2026-02-05Induced subgraphGiven a graph $G = (V, E)$ (directed graph or undirected graph ) and a subset of the vertices $X \subset V$. The induced subgraph of $G$ on $X$ is the subgraph of $G$ defined by $H = (X, \{(u,v) \in E \vert u,v \in X\})$.
- Leaf (graph)
Last edited: 2023-11-11In a graph we say a vertex $v \in V$ is a leaf if the degree of the vertex is 1, i.e. $\mbox{deg}(v) = 1$.
Visual exampleIn the graph below $4$ is a leaf vertex.
- Loop (graph)
Last edited: 2023-11-11A loop in a graph is an edge of the form $(v,v)$ i.e. the start and end vertices are the same. These are not permitted in simple graphs.
- Max clique problem (graph)
Last edited: 2026-02-05# Statement
Max clique size problemGiven an undirected graph $G = (V,E)$ what is the largest $S \subset V$ such that the induced graph on $S$ forms a clique .
- Minimum vertex cover problem
Last edited: 2026-02-05# Statement
Minimum vertex cover problemGiven an undirected graph $G = (V,E)$ provide a vertex cover of smallest size.
- Neighbourhood (graph)
Last edited: 2026-02-05NeighbourhoodFor a undirected graph $G = (V,E)$ the neighbourhood of $X \subset V$ is $N_G(X) = \{u \in V \vert (x,u) \in E, x \in X\}$ ($\backslash X$, $\cup X$). Sometimes this will be defined to include $X$ or exclude $X$ - this is called open and closed neighbourhoods.
- Path (graph)
Last edited: 2023-11-11Given a graph $G = (V, E)$ a path is a sequence of edges $\{e_i = (x_i, y_i)\}_{i=1}^k$ such that $x_i = y_{i+1}$ for all $1 \leq i < k$. We say the length of the path is $k$.
Visual representationLets use our simple graph below
There is a path that goes $(1,3), (3,4)$ from vertex 1 to vertex 4. Note there is an implicit directionality when we say this.- Proper vertex colouring
Last edited: 2026-02-05Proper vertex colouringGiven a undirected graph $G = (V,E)$ and vertex colouring $c : V \rightarrow D$. This colouring is called proper if for all $(u,v) \in E$ we have $c(u) \not = c(v)$.
- Rooted tree
Last edited: 2026-02-05Rooted treeA rooted tree is a tree $(V, E)$ with a root vertex $r \in V$. This is sometimes represented as $(T = (V,E), r)$. In a rooted tree
- Rudrata cycle
Last edited: 2026-02-05Rudrata cycleGiven a graph (undirected graph or directed graph ) $G = (V,E)$, a cycle $c$ is a Rudrata cycle if it visits every vertex exactly once.
- Rudrata cycle problem
Last edited: 2026-02-05# Statement
Rudrata cycle problemGiven a graph $G = (V,E)$, what is a Rudrata cycle if it exists?
- Rudrata path
Last edited: 2026-02-05Rudrata pathGiven a graph (undirected graph or directed graph ) $G = (V,E)$ a path $p$ is a Rudrata path if it visits every vertex exactly once.
- Rudrata path problem
Last edited: 2026-02-05# Statement
Rudrata path problemGiven a graph $G = (V,E)$, what is a Rudrata path if it exists?
- Tree (graph)
Last edited: 2026-01-28TreeA tree is a connected graph which has no cycles (i.e. is acyclic ).
- University of Warwick - PhD
Last edited: 2026-01-28# Overview
During my PhD at the University of Warwick, I explored graph theory and group theory under the supervision of Agelos Georgakopoulos. My research was an intellectually challenging and rewarding journey through complex mathematical principles.
# Academic Experience
The community at Warwick was a source of inspiration and support, filled with brilliant and kind individuals who fostered an environment conducive to growth and learning.
- Vertex Colouring
Last edited: 2026-02-05Vertex ColouringGiven an undirected graph a $G = (V,E)$ a vertex colouring using $D$ is a map $c: V \rightarrow D$. Whilst you can use a generic domain $D$ normally people talk about $k$-colourings, this is where $D = \{1,2, \ldots, k\}$.
- Vertex cover
Last edited: 2026-02-05Vertex coverGiven an undirected graph $G = (V,E)$ a set $C \subset V$ is a vertex cover if for all $(u,v) \in E$ we have $u \in C$ or $v \in C$.
- Vertex cover if and only if the complement is an independent set
Last edited: 2025-12-05# Statement
LemmaSuppose we have an undirected graph $G = (V,E)$ with $C \subset V$. Then $C$ is a vertex cover if and only if $\overline{C} := V \backslash C$ is an independent set .
- Vertex cover of a given size
Last edited: 2026-02-05# Statement
Vertex cover of a given sizeGiven an undirected graph $G = (V,E)$ and a positive integer $g > 0$, is there a vertex cover using at most $g$ vertices, if so what is it?
- Vertex cover of a given size is NP
Last edited: 2026-01-28# Statement
LemmaVertex cover of a given size is NP .
- Vertex cover of a given size is NP-complete
Last edited: 2026-01-28# Statement
Lemma - Clique (graph)