Questions tagged [graph-theory]
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.
23,235
questions
1
vote
1
answer
21
views
Edges of a $K_4$ cannot be too short
This problem arised while I was working through Erdös-Bollobas's solution for Ramsey-Turán Problem however i believe that details for that isn't necessary.
Consider the following construction
\begin{...
- 415
1
vote
0
answers
21
views
Meaning of $\mathbb{R}^E$ in graph theory
I'm reading through Lovasz's paper
on discrete analytic functions but I'm confused about how the coboundary of a node $\delta v$ is defined. What does $\mathbb{R}^E$ mean on page 243 where $E$ is the ...
- 301
0
votes
1
answer
34
views
Is the function of shortest distance path between two vertex sets convex?
The problem is formally as follows:
Consider a weighted undirected graph ${G}=({V}, {E})$ where ${V}$ is the set of vertices and ${E}$ is the set of edges with weights $w_e \in \mathbf{R}_{+}, \forall ...
1
vote
0
answers
20
views
Van der Waerden's theorem through Ramsey's Theorem
Van der Waerden's Theorem
Given positive integers $r$ and $k$, there is some number $N$ such that if the integers $\{1, 2, \dots, N\}$ are colored, each with one of $r$ different colors, then there ...
- 1,763
0
votes
0
answers
12
views
Zero as many correlations as possible while retaining as much correlation information as possible
I have a correlation matrix $C$ between $n$ variables, and I need to make this correlation matrix as sparse as possible while retaining the maximum overall correlation.
I know this is likely too vague ...
- 35
1
vote
1
answer
23
views
2-ish colourability algorithm
To check if a graph G is 2-colorable is to paint some random vertex green and its adjacent vertices red and so on until you get a valid 2-coloring of the graph or you reach a contradiction where 2 ...
- 1,960
1
vote
1
answer
42
views
How many spanning trees does a graph obtained from $K_n$ by adding an extra vertex adjacent to two vertices in $K_n$ have?
I've tried solving this with the Matrix-Tree Theorem using the Laplacian matrix, and found a result of $2*(n-2)^{n-2}$.
However, I feel as if I am approaching this in the wrong way. Any hints on ...
0
votes
0
answers
32
views
Proving that $r(cl(X) \cup cl(Y)) = r(cl(X \cup Y))$.
Here is the question I am trying to prove:
Let $M$ be a matroid, and $r$ and $cl$ be its rank function and its closure operator. Prove the following:
$(d)$ $r(X \cup Y) = r(X \cup cl(Y)) = r(cl(X) \...
- 1,767
-1
votes
0
answers
20
views
proving that $r(X \cup cl(Y)) = r(cl(X) \cup cl(Y)).$
Here is the question I am trying to prove:
Let $M$ be a matroid, and $r$ and $cl$ be its rank function and its closure operator. Prove the following:
$(d)$ $r(X \cup Y) = r(X \cup cl(Y)) = r(cl(X) \...
- 1,767
0
votes
0
answers
18
views
proving that $r(X \cup Y) = r(X \cup cl(Y)).$
Here is the question I am trying to prove:
Let $M$ be a matroid, and $r$ and $cl$ be its rank function and its closure operator. Prove the following:
$(d)$ $r(X \cup Y) = r(X \cup cl(Y)) = r(cl(X) \...
- 1,767
0
votes
0
answers
81
views
How many automorphisms does this graph have? [closed]
How to calculate it? Here is the picture:
I have been thinking. 0 cant move anywhere. 1 can swap only with 2. 3 only with 4. 5 only with 6. 7 8 and 9 can swap individually as needed. Now the problem ...
0
votes
1
answer
74
views
Is my proof that all trees have size $n-1$ correct?
Lemma All connected graphs admit a spanning tree.
Proof By induction.
For step 0, choose any $u\in G$ and set $V_0 = \{u\}$ and $E_0 = \varnothing$.
For step $n+1$,
Order the vertices in $V_n$ as $\{...
1
vote
0
answers
35
views
Perfect matching in a bipartite graph avoid increasing perfect matchings?
Let $A=\{a_1,\dots,a_n\}$ and $B=\{b_1,\dots, b_n\}$ be two disjoint vertex sets.
Let $A_i=\{a_1,\dots, a_i\}$ be the set of first $i$ vertices of $A$. And $B_i=\{b_1,\dots, b_i\}$, similarly.
For $1\...
- 1,833
0
votes
0
answers
40
views
Lower bound for couples of disjoint sets in some partitions of the power set
Consider partitions $\mathcal{F}=\{\mathcal{A_1},\ldots,\mathcal{A_n} \}$ of the powerset without the empty set element $Q = \mathcal{P}([n]) \setminus \{\emptyset\}$.
Let $\mathcal{F}_a = \{\mathcal{...
- 2,761
0
votes
0
answers
26
views
How can I make a n order Hamilton-connected graph by using no more than (3n+1)/2 edges
There is a theorem as "if G is a Hamilton-connected graph and $|V(G)|⩾4$, the following inequation holds: $|E(G)|⩾[\frac{3|V(G)|+1}{2}]$".But can the minimun bound can be got?
this is one of ...
2
votes
1
answer
66
views
Minimum vertex number that admits linear $d$-regular $k$-uniform hypergraph
$\newcommand\LRU{\mathrm{LRU}}\newcommand\tA{\mathrm{A}}\newcommand\tB{\mathrm{B}}\newcommand\tC{\mathrm{C}}\newcommand\tD{\mathrm{D}}\newcommand\tE{\mathrm{E}}$
For given integers $d>0$, $k>1$ ...
- 3,186
0
votes
0
answers
51
views
Allocating one source to each islanded subgraph
Suppose $G$ is a graph. $E(G)$ and $V(G)$ denote the sets of the edges and nodes (vertices) of $G$, respectively. Below is shown a graph with 9 nodes and 12 edges, which I will use as an example.
<...
1
vote
0
answers
94
views
Tools to investigate unusual algebraic structure
I will begin with a mostly motivational thought about the projective plane. In this plane, every two lines intersect at a singular point. Let's mark the lines set as $\mathcal{L}$ and the points set ...
- 178
7
votes
2
answers
1k
views
Why does Graph Theory Use the term Edge(s) to Describe Connectors (and not Line(s))?
Any insights into the historical rationale for using the term 'Edges' to describe connections between vertices...as distinct from the term 'Lines'?
- 195
0
votes
0
answers
23
views
Showing that every undirected simple graph $G$ contains a path of length $\delta(G)$ [duplicate]
This is proposition 1.3.1 of Diestel's graph theory, 5th edition. The claim is that every simple undirected graph $G$ contains a path of length $\delta(G)$, when $\delta(G)$ is the minimum degree of ...
- 725
0
votes
0
answers
14
views
Which of the following statements is not true about the relationship between the articulation points and the bridges?
In a simple connected graph that has more than two vertices, the endpoint of a cut edge must have at least one cut vertex.
...
2
votes
1
answer
56
views
Maximum number of vertices with degree three in maximal bipartite planar graphs
A bipartite graph $G$ is a graph where each cycle has an even length. If $G$ can be drawn on the plane without any crossings of edges, $G$ is called planar. $G$ is called maximal planar bipartite if ...
- 1,978
2
votes
0
answers
37
views
For simple, triangle-free graphs, prove $e(G) \le \alpha(G)\beta(G)$
For simple, triangle-free graphs, prove $e(G) < \alpha(G)\beta(G)$, where:
$e(G)$ - number of edges
$\alpha(G)$ - independence number (maximum size of independent vertex set in G)
$\beta(G)$ - ...
- 143
0
votes
1
answer
53
views
The values of $m,n$ that makes $U_{m,n}$ graphic.
I am trying to find the values of $m,n$ that makes $U_{m,n}$ graphic. I am guessing that it is only graphic if $n = m + 1,$ I tried $U_{2,4},U_{2,5},U_{3,6}, U_{2,3},U_{4,5}$ and I think I am correct. ...
- 1,767
0
votes
0
answers
39
views
Can we have a regular matroid $U_{1,2}$?
Here is the definition of a regular matroid:
Here is the definition of regular:
A regular matroid is one that can be represented by a totally unimodular matrix. And a totally unimodular matrix is a ...
- 1,767
-2
votes
0
answers
39
views
Every graph has a bipartite graph as an induced subgraph.
why is this true? I tried working it out for K5 and K3 but i cannot find a bipartite induced subgraph.
I was wondering if K2 would be considered a bipartite induced subgraph?
- 1
0
votes
1
answer
25
views
Moving edges of bipartite graph to the leftmost?
Given a bipartite graph $G$ with two sides $A=\{a_1,\dots, a_n\}$ and $B=\{b_1,\dots, b_n\}$.
I define a ``pressing" operation $f_{a_i,a_j}(G)=G'$ for $i<j$: $G'[A\cup B\setminus\{a_i,a_j\}]=G[...
- 1,833
-3
votes
0
answers
41
views
graph theory trees and cuts
Could someone explain why these statements are true or false?
Every tree has an vertex-cut of size 1 (False)
Every tree has an edge cut of size 1 (False)
I thought they were true?
- 1
0
votes
0
answers
39
views
using $P$ in place of $P^T$ when doing graph isomorphism through matrices
Let $G,H$ be simple graphs, and $A_G,A_H$ their adjacency matrices. Let $P$ be a permutation matrix, representing the permutation $\pi$.
I'm currently trying to understand why two graphs are ...
- 143
0
votes
1
answer
21
views
Lower bounds on the maximum eigenvalue of the adjacency matrix of an edge weighted graph
If $G$ is a simple graph with adjacency matrix $A$ then the following inequalities are known to hold (See eg. Prop 2.1. of this note of Lovász - there's no proof given though):
$$\sqrt{\Delta(G)}, d_{\...
- 1,486
1
vote
0
answers
22
views
Class of graphs with superpolynomial / subexponential number of maximal cliques
It is a classical result of Moon & Moser that the maximum number of maximal cliques in a graph with n vertices is $3^{n/3}$. There are several similar examples with exponentially many maximal ...
- 2,102
0
votes
1
answer
35
views
Constructing a basis for a matroid with a circuit in it.
Here is the question I am trying to solve (Matroid Theory, second edition by Martin Oxley, Chapter 1, section 2):
Prove that if $C$ is a circuit of a matroid $M$ and $e \in C,$ then $M$ has a basis $B$...
- 1,767
6
votes
1
answer
168
views
How many different "syntactic trees" exist related to an $m$ word sentence?
Before talking about the main topic, I would like to say that
I'm not in major of mathematics, nor any of mechanics.
So, there could be an issue of defining concepts or words not being strict or even ...
- 63
2
votes
1
answer
35
views
Inductive proof for statement about product of weights in intro to dimer model
I was reading this review by Kenyon on the dimer model, and there's a lemma at the beginning that I'm struggling to prove.
Here's the set-up. We have a finite 2D square lattice graph, bounded by a ...
- 31
2
votes
1
answer
236
views
What is the math behind the zombie tiktok filter game
I was recently just scrolling my life away on this app called TikTok on this miniature computer called my phone, and recently came accross a trend of people playing a game on a filter. The game is ...
- 55
2
votes
1
answer
62
views
Existence of magic labelings on graphs
Given some undirected simple graph $G$, a magic labeling is an edge labeling such that each edge is assigned some positive integer such that the sum of the labels of the edges adjacent to each vertex ...
- 21
-1
votes
0
answers
21
views
Applications of differential equations on graph theory [closed]
What is the application of differential equations on graph theory?
- 65
0
votes
0
answers
15
views
Relationship between number of perfect matchings in a balanced bipartite graph and determinant of its biadjacency matrix.
Let $G$ be a balanced bipartite graph with the adjacency matrix $A$. It is known that $A$ can be written in the form $A=\left[\begin{array}{ll}
0&B\\
B^T&0
\end{array}\right]$, where $B$ is ...
- 35
0
votes
0
answers
31
views
prove that every tree has at most one perfect matching verification
Prove that every tree has at most one perfect matching.
My logic is suppose we have a tree T. All leaves in T must be matched with the vertex they are connected to as they only have degree 1. Now ...
- 631
1
vote
0
answers
30
views
Prove bipartite graph with maximum degree d is a subgraph of a d regular bipartite graph
How can I show that every bipartite graph of maximum degree d is a subgraph of some d-regular bipartite graph.
If something I'm saying could be better mathematically phrased, please let me know. Let'...
- 631
0
votes
0
answers
35
views
Incidence Matrix and Graph cycles
Let $G$ be an undirected graph without loops and consider its incidence matrix $N_G$ be a $|V(G)| \times |E(G)|$ matrix such that
$$n_{ij}= \left\{\begin{matrix}
-1 & \text{edge $j$ starts from ...
- 350
1
vote
0
answers
48
views
Show Tree Proof is Incorrect
It seems the part that says every vertex in H has degree at least two is not necessarily true. The paths could converge prior to seeing vertex v, thus resulting in at least one vertex having degree 1. ...
- 631
2
votes
1
answer
56
views
Sum of squares of chromatic roots of a bipartite graph
Given a graph $G = (V, E)$, we can calculate its chromatic polynomial $P(G, k)$, and it has $n$ (complex) roots, also known as chromatic roots. It is a well-known fact that the sum of chromatic roots ...
- 77
4
votes
2
answers
299
views
What is the type of this directed graph?
Let $G=(V,E)$ be a directed graph. Suppose that $G$ has the following properties:
the vertex set $V$ is partitioned into $T$-parts $V_0,V_1, \dots, V_{T-1}$, and
for any edge in $E$, if its initial ...
- 41
-2
votes
0
answers
31
views
Erdős–Rényi graph with degree $O(1)$ High dimensional probability [closed]
Consider a random graph $G=G(n,p)$ with expected degrees $d=O(1)$.Show that, with high probability has a vertex whose degree is at least of order
$$\frac{\log n}{\log \log n}$$.
- 1
0
votes
0
answers
18
views
Number of Iterations to maximize flow given recurrence relation
I have proven that there is always an augmenting path of capacity at least $\frac{F}{|E|}$. How do I use this to bound the number of rounds given that I use a relation to increase the flow by a ...
- 89
10
votes
2
answers
2k
views
Can a hexagonal grid embed rectangular coordinates?
I'm trying to figure out if a hexagonal grid can embed rectangular coordinates in whole numbers of "Y-steps". In the image below, one "Y-step" is the spacing between red hexagon ...
- 267
5
votes
1
answer
184
views
Why does a 3-regular planar graph of diameter 3 have at most 12 vertices?
Today, I saw an interesting exercise on page 224 of the West textbook "Introduction to Graph Theory".
6.1.15. Construct a 3-regular planar graph of diameter 3 with 12 vertices. (Comment: T. ...
- 1,978
2
votes
0
answers
35
views
Knowledge graphs, logic and categories recommendation
I recently started to be more interested about "classical AI" and in particular about knowledge graphs/ontologies. I was looking for a modern (written after 2015 if possible) and highly ...
- 280
4
votes
1
answer
105
views
Icosahedron with asymmetric coloring
I am trying to determine the number of unique solutions when placing "dots" on the sides of an icosahedron. There can be up to three dots placed symmetrically on each side. The dots are ...
- 143