# Tagged Questions

Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

20 views

87 views

### Coloring a Complete Graph in Three Colors, Proving that there is a Complete Subgraph

Color the edges of a complete graph on $n$ vertices $K_n$ in three colors (red,blue,yellow) such that at most $\dfrac{n^2}{k}$ are colored red ($k$ is some natural number). Prove that $K_n$ ...
28 views

### Simple explanation of Dijkstra's Algorithm?

Can anyone provide a simple explanation of Dijkstra's Algorithm? My text, discrete mathematics with applications by Susanna Epp provides a very complex explanation of the algorithm that I cannot seem ...
14 views

### Why converting a minor of a graph into a subdivision is not always possible?

In my attempt to try to understand the Kuratowski's Theorem and the Wagner's Theorem, I encountered an article in Wikipedia where it is mentioned that converting a minor of a graph into a subdivision ...
36 views

### Some (trivial?) doubts on the proof of chromatic number of any planar graph is at most 6

I am trying to show that chromatic number of any planar graph is at most 6. This is a weaker statement of the Four-Colour Theorem. I have a vague idea about the proof but not sure how to convince ...
15 views

### Trying to understand some claims on chromatic number of union of graphs

Let $G_1=(V,E_1)$ and $G_2=(V,E_2)$ be graphs. Let $c_1:V\to[\chi(G_1)]$ and $c_2:V\to[\chi(G_2)]$ be proper colourings of $G_1$ and $G_2$ respectively. My questions: I am trying to understand the ...
67 views

### explicit upper bound of TREE(3)

TREE(3) is the famously absurdly large number that is the length of a longest list of rooted, 3-colored trees whose $i$th element has at most $i$ vertices, and for which no tree's vertices can be ...
34 views

### Books on graph/network theory with linear algebra focus

I am interested on getting feed back on books that are graph theory with focusing on linear algebra(have taken several courses on Linear Algebra) I have gone through Introductory Graph Theory by ...
111 views

### How many different isomers of $C_3 H_4 Cl_2 F_2$ exist?

I was on my high school chemistry class when I came across this problem, which, I think, belongs to group theory. The problem is that it is not possible to label the carbons as reflection should not ...
21 views

22 views

### Is this the correct directed graph for this relation?

The relations is defined by the set of ordered pairs $$R = \{(1,2),(1,3),(2,3),(3,4),(3,1),(3,2),(3,3),(4,4)\}.$$ Please excuse my drawing, I'm very sorry for it, I hope it's understandable though.
13 views

### Sufficient condition for directed graph having an even directed cycle.

I want to show that a directed graph $D$ on $n$ vertices with minimum out-degree $(\log_2 n) + 1$ always has an even directed cycle. I first saw this claim here with a version as an exercise here. I'...
19 views

### Let be $G$ a graph of order $n$. Show that if $\delta(G) = \frac{n}{2}$, then $\lambda(G) = \delta(G)$

I was reading the book graph theory by harary, and he prove the upper bound for the edge connectivity, and mentions that the equality holds when $\delta(G) = \frac{n}{2}$, Any ideas how to prove it.
220 views

### Bound on the size of Permutation Set for Isomorphism

$\textbf{Claim :}$ $G, H$ are partitioned into sub-graphs $\{ G_1,G_2 \cdots G_x \}$ and $\{ H_1,H_2 \cdots H_x \}$ . For each $G_i$ we constructed a set permutation, $\beta_i$ such ...
780 views

### maximum flow ford-fulkerson analysis

I am reading about maximum flows in Introduction to algorithms by Cormen etc. Ford-Fulkerson algorithm is given below. FORD-FULKERSON(G, s, t) ...
23 views

### Max Flow Min Cut - Prove that $e$ crosses some minimal cut

I already asked about the opposite direction but I'm really confused about it, so I'd like to get some help please: Let's assume we have a flow network $G$ and some edge $e$. Now, Let's assume ...
20 views

### Chromatic number of a graph after a vertex is deleted from it.

What happens to the chromatic number of a graph, G, when one of its vertices, v, is deleted? By this I mean what will be the chromatic number of the subgraph G-v? I know that the chromatic number can ...
13 views

18 views

### Which of the following cannot find for disconnected graph of n vertex.

Which of the following cannot find for disconnected graph of n vertex. Matching number of graph Covering number of graph Independent set number of graph All My attempt: Matching number: Given ...
28 views

### Graph with odd number of common neigbors

can you check my soultion? Task:In graph G every two vertices have odd number of common neighbors. Prove that every vertex has even degree. My thinking. I choose arbitrary vertex $v$ and build ...
54 views

Let $A$ denote the adjacency matrix of a connected graph $G$ with $n$ vertices and $e$ edges.If $i$ and $j$ are vertices of $G$ with $d(i,j)=m$. Then prove that the set of matrices $\{I,A,A^2,\... 1answer 31 views ### How to find the eigen values How to find the eigen values of the graph having vertex set as$\{1,2,.......n\}$and edge set as$\{(l,l+1)\} \cup (1,n)$? where$1\le l \le n$. Here I am considering the Laplacian matrix of ... 0answers 31 views ### Automorphism and Direct Product of Generating Set Notation:$H $are partitioned into sub-graphs$ H_1,H_2 \cdots H_x$. We see them in the adjacency matrix of$H$given below- $$H = \begin{bmatrix} H_{(x)} & R_{(x, x-1)} & R_{(x,x-... 0answers 12 views ### what is the time complexity of checking the conservation of flow in a network? As you may know, considering a network with the set of nodes V, the conservation of flow law is the followings:$$\sum_{v \in V} f(u, v) = 0, \quad \text{for all$u \in V \setminus \{s,t\}$}$$and ... 0answers 46 views ### Proving that a random graph is almost surely connected So, I'm trying to show that a random graph is almost surely connected. I want to know if my intuition is correct, and if so, how to formalize that intuition into a proof. If a graph$G=(V,E)$has$|V|...
Every graph whose chromatic number is more than ____ is not planner. My attempt: The answer should be $4$ by four color theorem. Somewhere, I read "Five color theorem"(See Theorem 6.3.8 at ...
If we pick a vertex $v$ and two consecutive neighbors of it, $u_1$ and $u_2$, are we sure that $(u_i, u_{i+1}) \in E$? Note: by consecutive I mean in a planar embedding; otherwise any two neighbors ...