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

1
vote
0answers
11 views

Bipartite graphs whose minimal cycles have length $4$

Is there some literature about bipartite graphs whose minimal cycles all have length $4$? By that I mean that any cycle in the graph with length strictly greater than four can be divided into cycles ...
0
votes
0answers
12 views

edge probability graph

I apologize if this is something very trivial, but I couldn't find an answer to it anywhere: I have a directed graph with n = 280 nodes and ...
0
votes
0answers
12 views

Small graphs containing all trees on $n$ vertices

What do those graphs look like which contain a copy of every tree on $n$ vertices and such that no proper subgraph has this property?
-3
votes
1answer
25 views

an edge coloring of $k_{16}$ with no monochromatic triangle

My plan is to show that $R(3,3,3)$ is more than 16. So, i want to prove it with graph-theory. i know i should find an edge coloring of $k_{16}$ which contains no monochromatic triangles. Can anyone ...
0
votes
0answers
8 views

Upper bound on the product of independence number and transversal for graph

I am trying to prove if $G$ is an $n$ vertex graph such that $|E(G)| \leq \alpha(G)\tau(G)$, then $|E(G)| \leq \frac{n^2}{4}$ where $\tau(G)$ is the smallest transversal in $G$. A transversal is a ...
0
votes
0answers
16 views

What is a Hungarian forest: definition

I have a doubt in the definition of the Hungarian forest. This is from the book Matching theory by Lovasz. Let $G$ be a bipartite graph with partite sets $A,B$ and let $M$ be a matching of $G$. Let ...
0
votes
0answers
10 views

Deleting vertex v from tree T leaves degree(v) components.

I don't really know how to approach this apart from: delete vertex v entails that you've deleted degree(v) edges, when you delete an edge form a tree you are left with exactly two components, .... ...
1
vote
2answers
28 views

smallest Bipartite Graph

Definition: A graph G is bipartite if its vertices can be partitioned into two sets V1 and V2 and every edge joins a vertex in V1 with a vertex in V2. Bipartite graphs can be characterized by all ...
0
votes
2answers
11 views

Each regional of a maximal planar graph is a triangle

Show that every region of a maximal planar graph is a triangle. A planar graph G is called maximal planar if the addition of any edge to G creates a nonplanar graph. Will this proof use the ...
3
votes
1answer
32 views

Prove that a one-color $K_4$ exists in a two-color $K_{18}$

An edge coloring of a graph is an assignment of colors to the edges of the graph. I have $K_{18}$ colored with blue and red and I want to show that it contains a $K_4$ colored with just one color. ...
0
votes
2answers
37 views

Can someone give a quick explanation of what this exercise wants from me?

I am having trouble understanding exercise 1.25 from the picture below. I know what order means, but the second sentence puzzles me. I have included the exercises before it in the case that 1.25 ...
1
vote
1answer
22 views

Need combinatorial formula

Let we have a forest $F_n(P)$ with $n$ nodes defined by set $P$ of all pairs $\{\text{father}, \text{son}\}$. For instance $P=\{\{1, 2\}, \{3, 4 \}, \{1, 3 \}\}$ defines a forest $F_5(P).$ Let ...
1
vote
0answers
28 views

Graphs of (un)bounded color valence

Talking about colored graphs there is a definition given for graphs with bounded color valence. This definition is as follows: A vertex-colored graph $G=(V,E)$ has bounded color valence, if there ...
0
votes
0answers
30 views

How to number the left-hand turn paths of planar bicubic graphs?

When you draw a planar cubic bipartite graph $\Gamma$ and 3-color its edges you can use this as an orientation $\mathcal O$. Definition A left-hand turn path on $(\Gamma, \mathcal O)$ is a closed ...
0
votes
1answer
20 views

Solve logistic problem with graph - fitting boxes

Suppose you have $n$ boxes, each of which falls into one of the $k$ sizes, and you want to nest smaller ones into larger ones, such that no two boxes $A$ and $B$ are nested inside the same box, if ...
0
votes
1answer
15 views

prove that k-cube has $2^k$ vertices, $k$ $2^k$ $^-$ $^1$ edges and is bipartite.

The k-cube is the graph whose vertices are the ordered k-tuples of 0's and 1's, two vertices being joined if and only if they differ in exactly one coordinate. Show that the k-cube has $2^k$ vertices, ...
0
votes
1answer
35 views

Translate this problem to graph theory

Say I have a size $k$ set called $S_k$ with elements that are natural numbers (repetitions are allowed). For instance $\{2, 8, 6, 6, 1, 3\}$ is a valid set for $k = 6.$ I am trying to find the least ...
1
vote
1answer
7 views

Size of minimum vertex cover on complete graph

I know that the maximum size of an independent vertex set, also known as the independence number and denoted by $\alpha$, plus the the size of the minimum vertex cover, $\tau$, is equal to the number ...
-1
votes
0answers
34 views

In graph theory, what would a negative number of vertices mean? [on hold]

I'm interested in expanding the concept of vertices into negative numbers. What properties would they have? I'm thinking perhaps extending V - E + F = 2 to begin.
0
votes
1answer
18 views

Let $G=(V,E)$ be the Rado Graph. Suppose $V_1 \cup V_2=V$. Show that one of the induced subgraphs of $G$ on $V_1$, $V_2$ is also Rado.

I started off with: one of $V_1$ or $V_2$ must be countably infinite. WLOG (without loss of generality) Let $V_1$ be countably infinite. I am not sure how to proceed after this.
0
votes
1answer
12 views

How to prove that adjacency matrix is L.I. if a graph contains no cycles?

Consider the vector space $F_n^2$ , and, as usual, let $e_i$ denote the vector with 1 at the $i$th coordinate, and 0 at all others. Call a vector of the type $e_i + e_j$ an edge vector, (think ...
0
votes
0answers
30 views

What is a “box” in this context “let $B ⊂ R^n$ be a box that can be partitioned into boxes”? [on hold]

Let $B ⊂ R^n$ be a box which can be partitioned into a finite number of boxes, each of which possesses a direction in which its length is an integer. Show that $B$ also has an integer length ...
2
votes
1answer
32 views

finding edges of a triangle graph from degrees of points

my theory: Given a list of points on a 2 dimensional plane, and the degree of each point, there should correspond only one way to arrange the edges between points so that the final graph is a mesh of ...
0
votes
2answers
32 views

threshold for random 2-sat

I'm looking at notes on the threshold for random 2-sat which is given as $r_{2}^{*}=1$. In the first part of proving the threshold they claim that a 2-sat formula is satisfiable if and only if the ...
1
vote
2answers
57 views

How Graph Isomorphism is used to determine Graph Automorphism?

From Lecture 2, Algebra and Computation by V. Arvind, (page2,3), I understood below passage- For our graph $G$, let $Aut(G) = H ≤ S_n$. We shall use Weilandt’s notation where $i^\pi$ denotes ...
0
votes
0answers
12 views

The problem of finding a smallest spanning 2-edge-connected subgraph of a graph G is NP-hard

For a given graph G = (V, E) with weights c(e), e ∈ E, the problem of finding a smallest spanning 2-edge-connected subgraph means that one has to find a subset F ⊆ E of smallest weight c(F) ...
-2
votes
0answers
19 views

Sending flow through a graph so that flow through each node is at most $f$

Given a graph $G$ with source $s$ and sink $t$, suppose we want to send $f$ units of flow from $s$ to $t$ such that at most $p$ units of flow are sent through each node. The edges have infinite ...
6
votes
3answers
153 views

Is there any algorithm to find Isomorphism function between two graphs?

Two graphs which contain the same number of graph vertices connected in the same way are said to be isomorphic. Formally, two graphs and with graph vertices are said to be isomorphic if there is a ...
1
vote
1answer
12 views

Can a minimal separator of a diameter 2 interval graph be large?

I'm getting used to chordal graphs (and some subclasses of chordal graphs). As we know, the concept of a minimal separator is central to chordal graphs. So recall a set $S \subseteq V(G)$ disconnects ...
0
votes
1answer
20 views

Proof of Mutually Inclusive Tree Properties

I don't know if that's the most accurate title. I'm trying to prove that one property of trees implies another without using any of the other properties. This is for homework. But I'm really just ...
0
votes
0answers
8 views

Stochastically removing edges from a complete graph; looking for info on this process

Given a complete graph of $n$ nodes and a time interval $T = \{t_1, \ldots, t_k\}$. Suppose each edge has a small probability $p$ of being removed from the graph at each time step and that this $p$ is ...
1
vote
0answers
22 views

Kelly's Proof Of Reconstruction Conjecture For Trees

The vertex reconstruction conjecture states that a graph on n>2 vertices can be discovered from only knowing its proper induced subgraphs. Kelly proved this for trees in 1961. I saw his proof and I ...
0
votes
0answers
11 views

Bound of diameter in Erdos-Renyi

I would like to compute the bound of the diameter in random graph $G(N,p)$ following Erdos-Renyi model. Anyone can tell me how to compute this bound? Thank you so much.
1
vote
2answers
22 views

Product of the edges is distinct

We have a complete graph with $n\geq 3$ vertices. Show that we can label the edges with $1,2$, or $3$ so that the product of the edges is distinct at every vertex. For $n=3$ this is obvious. For ...
0
votes
0answers
20 views

Degree of nodes in Erdos Renyi model

I see in the E-R model with a random graph $G(N,p)$ on $N$ nodes and probability of edge existence $p$, the probability that a node has degree $d$ is $$ P(d)=\binom{N-1}{d} p^d (1-p)^{N-1-d}$$ Give a ...
0
votes
0answers
12 views

Hamioltonian Circuit of Planar Graph of Order $2^n$

$G$ is a planar graph of order(= number of vertices) $2^n$. Questions: When $G$ has a Hamiltonian Circuit? Is there a polynomial or quasi polynomial time algorithm to decide whether $G$ has a ...
0
votes
1answer
19 views

To Prove G/e is acyclic

Let G be an acyclic graph and let e $\in$ E, Show that G/e is acyclic. Where "/" means contract in graph theory. How can I write an intuitive proof?
0
votes
1answer
13 views

Prove that every graph has two vertices that are endpoints of the same number of edges

Prove that every graph has two vertices that are endpoints of the same number of edges. My proof was that in any graph with $n$ vertices, each vertex $v$ has have $1 \leq \deg(v) \leq n-1$. By a ...
1
vote
0answers
17 views

Number of global min cuts in undirected graph

I'm looking at a proof of the following theorem "The number of global minimum cut is $\le \binom{n}{2}$". It says $\forall i$ from $1$ to $n-1$ Find min-cut seperating $\{1,2,\cdots,i\}$ from $i+1$. ...
0
votes
0answers
20 views

Real world application of independent sets

Independent sets are closely related to dominating sets. What are the real world applications of independent sets? Correspond to the question: Real world application of dominating set?
1
vote
1answer
17 views

Inequality with edges and chromatic number.

I have proved the statement : Every graph $G$ with $\chi(g)=k$ has at least $\binom{k}{2}$ edges. I did this my saying for any 2 colours, there exists an edge connecting one vertex of one colour to ...
0
votes
0answers
20 views

Third coefficient of the chromatic polynomial

If G is a graph and $\chi(G,k)=\sum _{i=0} ^{n-1} a_i k^{n-i}$ I know that $a_0 = 1$ and $a_1 = -|E(G)|$ I'm looking for a formula for $a_2$ using |V|, |E| and the number of independent sets of ...
0
votes
0answers
2 views

Graph Theory: What is the best kind of network centrality to use to determine flows? sources/sinks?

I am working on a medium-sized (80 vertices), cyclic, directed network with commodities being passed around between agents. Its actually stock market data. I would like to determine who of the ...
0
votes
0answers
12 views

Extra zero when calculating a linear trendline

I am attempting to write an algorithm in $c++$ to calculate a linear trendline. The issue is when I am doing examples by hand, I get a slope that is $10^4$ whereas I believe it should be $10^3$. The ...
0
votes
1answer
18 views

Vertices of equal degree in a graph

I have found the proof that if G is a simple graph with order $n\geq 2$ then there are at least two vertices in $V(G)$ that have equal degree. Does this statement extend to non-simple graphs? If so, ...
0
votes
1answer
19 views

For an odd degree node .

Let $v$ be an odd degree node. Consider the longest walk starting at $v$ that does not repeat any edges (though it may omit some). Let $w$ be the final node of the walk . Show that $v$ $\neq$ $w$. My ...
1
vote
1answer
40 views

Chromatic Index in Graph

There is a graph $G$ with maximum degree that is greater than $0$. Suppose that $G$ contains a perfect matching $P$ and that $G-P$ (graph after removing all edges of $P$ in $G$) is bipartite. What is ...
1
vote
0answers
30 views

What is the probability of no cycles length $n$ in a simple, directed Erdos-Renyi graph with $n$ vertices?

What is the probability of having no cycles with length $n$ (touching all vertices) in a simple, directed Erdos-Renyi graph with $n$ vertices? For example, if $n=2$, then the probability is ...
1
vote
0answers
38 views

Non trivial results in graph theory/combinatorics coming from number theory

Are there any non-trivial results in graph theory that can be deduced from number theory or arithmetic geometry? I am not looking for expander graphs or applications however I am looking for ...
0
votes
0answers
16 views

Tournament graph with strong vertex in any subset

Consider a tournament graph with $110$ vertices. In any set of $55$ vertices, there exists a vertex that has an out-edge to at least $50$ of the remaining $54$ vertices. Prove that there exists a ...