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.

Filter by
Sorted by
Tagged with
0 votes
0 answers
7 views

Bounds on chromatic number in terms of chromatic numbers of subgraphs.

Suppose we have a graph G of the form $G = G1 \cup G2$, and graphs G1 and G2 are defined by $V(G1) = V(G2)$. How can we describe the dynamics of the chromatic number of G in relation to the chromatic ...
organdonor's user avatar
0 votes
0 answers
39 views

Corollary of Ore's Theorem

"Theorem (Ore; 1960) Let G be a simple graph with n vertices. If $$\operatorname{deg}(v) + \operatorname{deg} (w) ≥ n$$ for every pair of non-adjacent vertices v, w, then G is Hamiltonian." ...
J P's user avatar
  • 83
0 votes
0 answers
12 views

Graph theory proof : graph with vertices of degree 4

Let $\mathscr{G}$ be a graph with $deg(v) = 4$ for all vertices. The graph has no loops. Proof that you can colour the edges with $2$ colours such that every vertex lies on 2 edges of one colour and ...
user34's user avatar
  • 111
0 votes
0 answers
18 views

What does the proportion between the mean size of the clusters and the number of clusters mean in the site percolation model?

I am trying to find a way to quantify the degree of clustering in the site percolation model for a planar lattice, such as a square. I am considering taking into account the ratio between the average ...
Mateo's user avatar
  • 25
0 votes
0 answers
16 views

Proof graph theory verification

So, I have to proof the following statement is true for all multigraphs. "Let $\mathscr{G}$ be a multigraph, if the removal of $n$ vertices results in $m > n$ connected components, than $\...
user34's user avatar
  • 111
0 votes
1 answer
31 views

Connectivity of bipartite graph

We consider $G$ to be a bipartite graph that is $(d \geq 1)$-regular and has at most $4d-1$ vertices. We wish to show that $G$ must be connected. My thinking was to prove by contradiction. So $G$ has ...
Jeff's user avatar
  • 167
0 votes
0 answers
39 views

Number of ternary rooted unlabeled trees

I derived a recurrent formula for the number of rooted unlabeled trees with n vertices. Removing the root, getting subtrees, I used combinations with repetitions and got the sequence 1,1,2,4,9,20... ...
matematik's user avatar
0 votes
0 answers
9 views

N point graph with different distances: prove there are no intersections

Given n points in the graph. Given that all distances between each two points are of different values. In graph we draw one line from each point to the nearest point. We should prove that there are no ...
renathy's user avatar
  • 281
-2 votes
0 answers
29 views

Reflecting light problem [closed]

Suppose you have an $(n\times m)$ matrix and 4 light sources from 4 different corners reflecting at $45 ^\circ$ Prove that the light covers all matrix if $n \nmid m$, where $m \geq n$
odrim's user avatar
  • 1
-4 votes
0 answers
49 views

Prove that the complement of a disconnected graph is connected.

The complement of a graph G is the graph Ḡ with the same vertex set V (Ḡ) = V (G) and edge set E (Ḡ) = (V(G)_2)\ E(G). Prove that the complement of a disconnected graph is connected. enter image ...
Giulia Colzani 's user avatar
1 vote
1 answer
16 views

Infinite lattice with every totally ordered set finite

Construct a lattice L such that L is infinite but every totally ordered subset of L is finite? I really don't know how to proceed because i don't see how every totally ordered set would be finite ...
Sj2704's user avatar
  • 11
3 votes
0 answers
70 views

Maximum cost flow in acyclic tournament

Given a digraph with vertices numbered from $1$ to $n$, where the edge $(i,j)$ exists if and only if $i<j$, which is called an “acyclic tournament with order $n$”. The problem is to find the ...
Alex-Github-Programmer's user avatar
0 votes
1 answer
30 views

Find all the nonisomorphic complete bipartite graphs $G=(V,E)$ where $ |V|=6$

I am confused by this question. The answer guide says that there are 3 graphs. i) $K_{1,5}$ ii) $K_{2,4}$ iii) $K_{3,3}$. I don't see how I can draw them to be non isomorphic. This question is from ...
LordAgame's user avatar
0 votes
3 answers
49 views

How to graph an irregular equilateral convex polygon inscribed in a ellipse? [closed]

What would be the steps or equation to graph a irregular convex equilateral polygon inscribed in a ellipse. I have not been able to find a example or equation of this online other then unanswered ...
ItsameLuigi64's user avatar
1 vote
0 answers
32 views

A Definition of a Graph Homology

Let $G$ be a graph, and define $C_n$ to be the free abelian group on labeled $K_k$ minors of $G$. We can define a boundary map $\delta_n$ from $C_n$ onto $C_{n - 1}$ by taking a $K_k$ minor and ...
Sean Longbrake's user avatar
4 votes
1 answer
59 views

Graph Minors and Subdivisions

Let $G$ be a graph that contains $H$ as a minor. Does there exist a subdivision $H'$ of $H$ such that there is a homomorphism $φ$ of $H'$ onto the $H$ minor, in particular, such that $φ$ is surjective ...
Sean Longbrake's user avatar
3 votes
2 answers
120 views

Un-definability of graphs with bounded out-degree

I want to solve the following question but has some difficulties: Given a language L = ⟨R( , )⟩ where R is a two-place relation symbol. Prove that the set of graphs of bounded out-degree (graphs whose ...
haha's user avatar
  • 133
0 votes
1 answer
44 views

Notion of neighborhood in Hall's Theorem

In Hall's Theorem, should we refer to $N(S)$ as $\bigcup_{x \in S}N(x)$ or as $\bigcup_{x \in S}N(x) - S$? I guess that the second definition is the one used in the theorem.
J P's user avatar
  • 83
0 votes
1 answer
43 views

If a simple graph $G$ is not connected, then $\overline{G}$ is connected

Let $G=(V,E)$ be a simple graph with $E \subseteq P_2(V)$ and define $\overline{G}=(V,\overline{E})$ as the complement graph. Show that if $G$ is not connected, then $\overline{G}$ is connected. I ...
J P's user avatar
  • 83
1 vote
2 answers
59 views

Constant weight codes with distance $4$ and weight $2$, $A(n,4,2)$

Maybe a strange question but on https://oeis.org/A001839 for $A(n,4,3)$ the first comment says that "Maximal number of edge-disjoint $K_3$'s in a $K_n$." and in my understanding, this ...
Jfischer's user avatar
  • 1,106
0 votes
0 answers
7 views

Non empty deficiency in proof of Lemma 3 of a Algorithmic Aspects of Vertex Elimination on Directed graphs.

Reading through the paper Algorithmic Aspects of Vertex Elimination on Directed graphs. There 's a detail in Lemma 3 which I don't know why it would be guaranteed to be true. Most of the terminology ...
user8469759's user avatar
  • 5,263
-2 votes
0 answers
35 views

Let G be a connected plane graph such that every region has at least five edges on their boundary prove that $3E\leq 5V-10$ [closed]

Complete answer for my university examination
Kunal's user avatar
  • 1
-2 votes
0 answers
15 views

A. Set of Vertices. B. Set of Edges. C. Size of the graph. D. Order of the graph [closed]

[graph-theory][1] [23]:https://docs.google.com/forms/d/e/1FAIpQLScjJOho5uH10ZqY- 28 kV8zDDFH-16_IuDp4uLxJCikh_x4DuhBA/viewform?pli=1. 23
Aly Pantahon's user avatar
0 votes
0 answers
23 views

Do Fagin's zero-one laws hold on stochastic block model?

Let $n$ be a positive integer (the number of vertices), $k$ be a positive integer (the number of communities), $p = (p_1, . . . , p_k)$ be a probability vector on $[k] := \{1, . . . , k\}$ (the prior ...
SagarM's user avatar
  • 1,777
-6 votes
0 answers
26 views

Exploring Ramsey Theory in Grahps [closed]

In the context of Ramsey theory, let R(m,n) denote the minimum number of vertices N for which graph with N vertices is guaranteed to contain either a clique of size m or an independent set of size n. ...
D.d's user avatar
  • 1
0 votes
1 answer
38 views

How many simple graphs are there such that the vertex set is $\{1,2,3,\ldots,n\}$ and every vertex has degree $2$?

If every vertex have degree $2$, I think that it should be simple cycle. So i searched about it, and i found that the number of it is $\displaystyle\frac{(n-1)!}{2}$. I want to know why the formula is ...
MathFaker's user avatar
0 votes
0 answers
19 views

Eigen Analysis of Block Bi-Symetric Matricies where each matrix is Circulent Symetric

Given a Block-Matrix that is Bi-Symetric with respect to the blocks. An Example for a 4x4 block matrix... $$ \begin{bmatrix} A & B & C & D \\ B & E & F & C \\ C & F & E ...
Aidan R.S.'s user avatar
1 vote
0 answers
29 views

Finding the maximal graphs to find the Ramsey number $R(P_4,C_7)$

For my introduction to combinatorics class, we are being asked to compute the Ramsey number for $R(P_4,C_7)$ where $R(P_4,C_7)=k$ is the minimum number of vertices needed such that the 2-coloring of $...
DoubleV's user avatar
  • 440
1 vote
1 answer
24 views

Gallai--Milgram theorem: relation between path cover number and independence number?

Gallai--Milgram theorem states that for any directed graph $D$, there exists a family of vertex-disjoint paths $P_1,\dots, P_k$ such that $\cup_{i=1}^nV(P_i)=V(D)$ and there exists an independent set $...
Connor's user avatar
  • 1,933
1 vote
1 answer
26 views

Alternatives to minimum spanning tree and neighborhood graphs

I am looking to represent data drawn from a high-dimensional manifold with a weighted graph. The shortest path distances in the graph are meant to approximate geodesic distance. I've tried both ...
JLinsta's user avatar
  • 718
3 votes
1 answer
42 views

The size of independent set in Claw-free graph

A claw-free graph is a graph that does not have a claw as an induced subgraph or contains no induced subgraph isomorphic to $K_{1,3}$. Let $\alpha(G)$ denote the maximum size of an independent set in ...
Mixi Andrew's user avatar
1 vote
1 answer
61 views

Closed Set in Product Topology

I am trying to understand the Compactness Argument in a Graph Theory Problem using Probabilistic Methods. $V$ is infinite set. For each finite subset $X \subset V$, let $C_X \subset [2]^V$ be the ...
tom_choudhurry's user avatar
0 votes
0 answers
17 views

Relationship between gauss elimination and vertex deficiency in associated graph

Currently reading through this document : https://www.jstor.org/stable/2100866 First few definitions (extracted from the paper) Given an undirected graph $G = (V,E)$ for each $v \in V$ we define $$ A(...
user8469759's user avatar
  • 5,263
0 votes
0 answers
22 views

How do I do a traversal like DFS in a DAG on an undirected graph

I apologize for my lack of knowledge, but I'm not sure what the graph traversal I need is called, so I'm having difficulty finding any information about it. I have an undirected, biconnected graph. ...
user1806566's user avatar
0 votes
0 answers
52 views

Graph with a vertex sequence (3,3,2,2,2,2,2,2,2)

Is it possible to create a graph with a vertex sequence (3,3,2,2,2,2,2,2,2) such that there is exactly one path between every pair of vertices with distance 3 or more? And if so could it be ...
nechlu's user avatar
  • 1
-2 votes
0 answers
24 views

Removing a clique C from a k-critical Graph G. Show that G - C is still connected?

I am still new to graph theory and have an upcoming test tomorrow. The task is as follows: G is a k-critical Graph including a Clique C. Is G - C (G without C) still connected? I know that it is, but ...
henri12i's user avatar
0 votes
1 answer
44 views

Using Euler formula to prove maximum number of lines in planar graph without triangles

Im trying to prove a planar graph without triangles with $ n \ge 3$ points has at most $2n-4$ edges. I want to solve this using the Euler formula, $n+f=m+2$. I've come to the conclusion that $f\le$ $m/...
Layla16's user avatar
  • 23
-3 votes
0 answers
78 views

The Ant's Mathematical Quest: Navigating an Infinite Tree of Odd Numbers

Enigma: In a mathematical tree, an ant begins at its home, represented by the number 1, and seeks to find a grain of rice placed upon any odd-numbered leaf. This is no ordinary tree: the branches are ...
PMF's user avatar
  • 15
2 votes
1 answer
131 views

Let G be a connected graph in which every vertex has degree three. Show that if G has no cut-edge then every two edges of G lie on a common cycle.

"Let $G$ be a connected graph in which every vertex has degree three. Show that if $G$ has no cut-edge then every two edges of $G$ lie on a common cycle." I have an idea for this proof but I'...
organdonor's user avatar
-2 votes
0 answers
21 views

Find two edge-disjoint spanning trees in $H_4$, the 4-dimensional hypercube. Draw $H_4$ and the trees. [closed]

Your help will be highly appreciated.
Aamir Hussain's user avatar
-1 votes
0 answers
31 views

Let $G = (V, E)$ be a bipartite graph. Show that we must have $|A| = |B|$ [closed]

Let $G = (V, E)$ be a bipartite graph with parts $A$ and $B$, hence, $V=A\cup B$. Assume that the degree of every vertex of $G$ is precisely $r$ (here $r$ is a positive integer). Show that we must ...
Aamir Hussain's user avatar
2 votes
1 answer
37 views

Showing the isomorphism between (the geometric lattice)$\pi_n$ and the lattice $\mathcal{L}(M(K_n)).$

Here is the question I am trying to solve: Show that the lattice of flats of $M(K_n)$ is isomorphic to the partition lattice $\pi_n$. Definition: $\pi_n$ is the set of partitions of $[n]$, partially ...
Secretly's user avatar
  • 3,683
0 votes
1 answer
27 views

Source of theorem regarding triangle presence in the graph

I know that there exists theorem that states the following: Graph $G$ contains triangle if and only if there are indices $i$ and $j$ existing so the both matrices $A_G$ and $A_G^2$ will have nonzero ($...
Keithx's user avatar
  • 159
0 votes
1 answer
22 views

How Does Adding Non-Parallel, Non-Intersecting Edges Affect the Number of Triangles in a Graph?

How should I approach the problem of predicting or calculating the change in the number of triangles when a new edge is added under these constraints? Are there specific combinatorial methods or ...
Steven Oh's user avatar
  • 105
2 votes
0 answers
111 views

Graph theory proof - if $G$ is $2$-connected then for each $u$ there exists $v$ and a cycle $C$ that includes $u, v$ and all of $v$'s neighbors

Need to prove that if $G$ is $2$-connected then then for each $u$ there exists a $v$ and a cycle $C$ that includes $u$, $v$ and all of $v$'s neighbors. I have reached an insight that all vertices must ...
Poncho's user avatar
  • 43
-1 votes
0 answers
16 views

A graph theory problem, I know the conclusion is obvious, but I cannot accurately describe its proof. [closed]

Show that a graph is planar if only if every subdivision of the graph is planar.
XCYUKK's user avatar
  • 1
0 votes
0 answers
28 views

Shortest super-path to complete multiple paths to vertices.

I have a graph with multiple vertices. Let's say all vertices are connected to each other, and all edges are equal weight. I have multiple directed paths I have to take across this graph, but I want ...
Eric Cochran's user avatar
1 vote
1 answer
40 views

Identifying isomorphisms between graphs

I have three graphs illustrated above and my goal is to identify if they are isomorphic or not. For disprove that they are isomorphic, I could point out properties such as having a cycle of a certain ...
J P's user avatar
  • 83
0 votes
1 answer
38 views

Counting number of spanning trees of graph

In the graph above, I should count the number of possible spanning trees. Firstly, I looked at the cycles on the rightmost side and I have $2 \times 3$ for that half; but there are also cycles on the ...
J P's user avatar
  • 83
0 votes
0 answers
19 views

Generating network centrality measures - should incoporate directed ties from unidentifiable nodes?

I have classroom network data where kids named their friends in the classroom (a directed network). I'd like to measure the closeness and betweenness centrality of each kid within their classroom. In ...
Marcus's user avatar
  • 1

1
2 3 4 5
471