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.

learn more… | top users | synonyms

2
votes
2answers
20 views

Hamilton-connected graphs have a chromatic number at least 3

A Hamilton-connected graph is a graph where for every pair of vertices there exists a hamiltonian path that connects them. I'm trying to prove that the chromatic number of a Hamilton-connected graph $...
0
votes
0answers
10 views

How to prove criteria of vertex being not in all maximum matchings?

So, i know, next fact is correct, but don't really know, how to prove it: Let $M$ be matching of graph $G$, vertex $u$ is $M$ - unsaturated. Then, if there is no augmenting path for $M$, which starts ...
2
votes
1answer
23 views

strongly regular graph with vertices subset of {1,2,…,7}

I have the following homework question: Let G be the graph obtained as follows. Let A={1,2,...,7}. Let the vertices of G be all the subsets of A of size 3 and 2 vertices be adjacent if and only if ...
3
votes
4answers
72 views

How can ($A$ and $B$ $\implies$ $C$) and ($C$ and $B$ $\implies$ not $A$) together imply (not $A\iff B$)?

I encountered this two statements when I tried to understand the proof of Kuratowski Theorem. Any minimal nonplanar graph and it has no Kuratowski subgraphs, then it must be at least 3 connected. An ...
0
votes
0answers
103 views

What kind of graph is the StackExchange?

Assuming that we have three distinct layers of nodes called Users, Questions & Answers, connected by the obvious way $(A)$, what kind of graph is the StackExchange? Do such graphs have special ...
1
vote
2answers
20 views

Prove that every vertex of a 2-regular graph G lies on an exactly one circle

My only idea so far is that if a vertex $v$ would lie on more than one circle, i. e. on 2 circles, then those 2 circles must separate in some vertex in order to be different and that cannot be because ...
1
vote
0answers
18 views

Is there a minimum spanning tree including $e$ after removing at most $k$ edges?

Let an undirected, connected graph $G=(V,E)$ with the weight funciton $w:E\to \mathbb{R}$, an edge $e$, and $0<k\in\mathbb{N}$. Describe an algorithm determines if there are at most $k$ edges could ...
1
vote
1answer
1k views

Using BFS or DFS to determine the connectivity in a non connected graph?

How can i design an algorithm using BFS or DFS algorithms in order to determine the connected components of a non connected graph, the algorithm must be able to denote the set of vertices of each ...
1
vote
1answer
21 views

Is the hypercube graph $Q_n$ k-factorable for k=modn?

Definition of k-factorable graph: https://en.wikipedia.org/wiki/Graph_factorization I have proved that a hypercube of any dimension has a perfect matching, thus also a 1-factorization. Can it be ...
0
votes
0answers
26 views

Graph Consistency Proof

Let $G = (V, E)$ be a graph. Assume that $G$ is bipartite, consistent and each vertex $G$ has a degree in 2016. Let $v ∈ V$ and $H = (V - v, E - {e ∈ E: v ∈ e}).$ Show that the graph $H$ is consistent....
0
votes
0answers
20 views

Prove that every maximal outerplanar graph has a 3-coloring

A maximal outerplanar graph is an outerplanar graph (which is a graph with a planar drawing with all vertices belonging in the outer face), where adding any edge would make it stop being outerplanar. ...
2
votes
2answers
41 views

The existence of a cycle in a graph

Let $C$ and $D$ be different cycles in the graph $G$, and $e$ a common edge of cycles $C$ and $D$. Show that $G$ contains a cycle not passing through the $e$. I think, it's not easy task, because ...
5
votes
1answer
62 views

Intuitive explation for oriented matroids?

Where can you find intuitive explanation on oriented matroids? Other perhaps relevant questions on this How do you get the chirotope of a oriented matroid from the signed circuits? (other than ...
1
vote
2answers
271 views

Oriented graph VS directed graph?

Alright, while the definitions are stated in my lecure notes, textbooks and wiki, I'll be honest, it just explodes my mind with what seems like word sorcery. Definition A directed graph is ...
0
votes
0answers
8 views

Are Oriented Graphs Related to Oriented Matroids?

My professor said that oriented matroids make it easier to investigate things such as connectivity. Recall that an oriented graph is a digraph without multiple edges or loops. Now Are oriented graphs ...
1
vote
0answers
21 views

If G be k vertex critical is it k edge critical too?

G is k- vertex critical if and only if for every vertex such v $\chi(G-v) < \chi(G)$ as same we can define k edge critical note that we know if G be k edge critical it is k vertex critical too ...
1
vote
0answers
20 views

Subgraph with “dangling edges”?

I was wondering if there is a notion in graph theory where one can have a subgraph such that the endpoints of all of the edges in the subgraph are not necessarily included in the vertex set of the ...
0
votes
1answer
705 views

Intersection and Union of sub graphs

can anyone phrase a common definition for the union and intersection for below case. Actually I am looking for mathematical expression in mathematical notations. For example if I want to do $G_1 \...
2
votes
1answer
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$ ...
1
vote
1answer
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 ...
1
vote
0answers
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 ...
3
votes
2answers
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 ...
1
vote
0answers
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 ...
3
votes
1answer
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 ...
1
vote
0answers
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 ...
6
votes
2answers
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 ...
0
votes
1answer
21 views

vertex cover of size k in a degree two vertices graph

Let $G=(V,E)$ be a simple graph where $\forall \ v\in V:\ degree(v)=2$. Consider the question: "Is there a vertex cover for $G$ like that of size k?" My approach Because $\sum_{v\in V}degree(v)...
3
votes
0answers
20 views

Cardinality of Set of Rooted Spanning Trees of Integer Lattice

I am wondering whether there are countably many or uncountably many spanning trees of the integer lattice rooted at a particular vertex, say the origin. In a spanning tree rooted at the origin there ...
0
votes
0answers
27 views

how to find the angle of Lovasz umbrella

in the book Thirty-three Miniatures: Mathematical and Algorithmic Applications of in problem 28 The Secret Agent and the Umbrella page 132 (pdf 140) we want to find an orthogonal reperesentation of ...
7
votes
1answer
137 views

How many colors in 3-d space to paint boxes?

Let's imagine that we have boxes shaped as rectangular cuboids and colored with many different colors (one color for one box). Boxes can touch themselves by faces. Their edges are parallel to axes $\...
0
votes
1answer
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.
0
votes
1answer
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'...
3
votes
1answer
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.
1
vote
1answer
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 ...
4
votes
2answers
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) ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
2answers
13 views

Max Flow Minimum Cut - after removing an edge

Suppose that the max flow of a network is $|f|$ and there's a minimum-cut $(S,T)$ such that $e$ is an edge which crosses the cut. Why is it must be that the max flow after removing $e$ is exactly $|...
0
votes
1answer
56 views

How many Fano Planes Can We Build with the Numbers from $1$ to $35$

The Fano plane is the finite projective plane of order 2, having the smallest possible number of points and lines, 7 each, with 3 points on every line and 3 lines through every point. Assume that ...
1
vote
0answers
28 views

A graph $G$ is $r$-factorable iff $G$ is $k$-regular and $k$ is a multiple of $r$

An $r$-factor of a graph like $G$ is a spanning subgraph of $G$ which is $r$-regular. A graph $G$ is called $r$-factorable if we can decompose edges of $G$ to $r-$factors. Prove that : A graph ...
0
votes
1answer
19 views

How many minimum spanning tree of following graph is possible.

How many minimum spanning tree of following graph is possible. My attempt: I've tried it manually as : Therefore, Total possible number of minimum spanning trees are $=2\times2\times2+...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
54 views

Prove that the set of matrices $\{I,A,A^2,\ldots A^m\}$ is linearly independent.

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,\...
0
votes
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 ...
2
votes
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-...
0
votes
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 ...
1
vote
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|...
0
votes
1answer
35 views

Four color theorem and five color theorem

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 ...
1
vote
1answer
32 views

In a maximal planar graph, are two consecutive neighbors of a vertex necessarily adjacent?

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 ...