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

0
votes
1answer
82 views

N-Regular graph problem

Suppose that G be a bipartite graph with maximum degree of k. Prove that: 1)Exists a K-regular bipartite graph that G be subgraph it(H)
0
votes
1answer
680 views

What is the definition of a network in graph theory

From Wikipedia a flow network (also known as a transportation network) is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot ...
1
vote
1answer
651 views

Defining a cut-set without referring to partitioning vertices into two groups?

From Wikipedia: a cut is a partition of the vertices of a graph into two disjoint subsets. The cut-set of the cut is the set of edges whose end points are in different subsets of the ...
0
votes
1answer
83 views

Arc transitivity of the complete graph

Recall that a graph $G$ is arc transitive if the natural action of $\mathrm{Aut}(G)$ on $A(G) = \{ (u,v) | \{u,v\} \in E(G)\}$ is transitive. In other words, given $(u,v),(u'.v') \in A(G)$ one finds ...
7
votes
3answers
2k views

Eigenvalues of a bipartite graph

Let $X$ be a connected graph with maximum eigenvalue $k$. Assume that $-k$ is also an eigenvalue. I wish to prove that $X$ is bipartite. Now if $\vec{x}=(x_1,\cdots ,x_n)$ is the eigenvector for ...
0
votes
1answer
153 views

Network Simplex Method: How to relabel the vertices and arcs such that the truncated matrix is upper triangular and non-singular.

Suppose $G = (V, A)$ is the acyclic weakly connected digraph with$ V $consisting of vertices $v_{i}$ $(i = 1, 2, ..., 8)$ in which the seven arcs are $(v 1 , v 2 ), (v 3 , v 2 ), (v 4 , v 3 ),(v 7 , v ...
1
vote
1answer
45 views

Alternative interpretation of graph-minor theorem

I have read some paper claim about graph-minor theorem that "Another equivalent form of the theorem is that, in any infinite set S of graphs, there must be a pair of graphs one of which is a minor of ...
1
vote
2answers
6k views

Hamilton,Euler circuit,path

For which values of m and n does the complete bipartite graph $K_{m,n}$ have 1)Euler circuit 2)Euler path 3)Hamilton circuit I found answers and you Prove(or show)that: 1)($K_{m,n}$ has a Hamilton ...
2
votes
1answer
397 views

Connectedness of a regular graph and the multiplicity of its eigenvalue

Suppose $X$ is a $k$-regular graph with adjacency matrix $A$. I wish to show that if $k$ has multiplicity $1$ as an eigenvalue of $A$ then $X$ is connected. By way of contradiction I assume that X is ...
0
votes
1answer
732 views

Every edge with even degree -> Euler tour

Euler tour is a closed walk that can traverse each edge in a graph exactly once. If every edge in a connected undirected graph has even degree, how can you prove that it has an Euler tour?
1
vote
1answer
187 views

Usage of Cauchy-Schwarz on graphs

Preface. I am reading up on the Chung-Graham-Wilson results on quasi-random graphs, and the description I'm reading is applying an apparently obvious usage of Cauchy-Schwarz that I'm just not seeing. ...
3
votes
1answer
1k views

The number of non-isomorphic spanning trees in K4

K4 has 16 spanning trees. I believe there are two non-isomorphic spanning trees in K4. Is this because half of the spanning trees have the sequence (1,2,2,1) as the degrees of their vertices, while ...
1
vote
2answers
80 views

For which $n$ is the graph $C^2_n$ planar?

Let $C_n$ be the simple cycle with $n$ vertices. Let $C^2_n$ be the graph obtained from $C_n$, and includes all the edges $C_n$ plus the edges $\{(u,v) : \mathrm{dist}(u,v) = 2\}$ in $C_n$. For which ...
1
vote
1answer
37 views

If $G$ is a tree and $\forall v_1, v_2 : dist(v_1, v_2)$ is even, where $v_1, v_2-$ are leaves $\Rightarrow \exists!$ a maximal independent set.

If $G$ is a tree and $\forall v_1, v_2 : dist(v_1, v_2)$ is even, where $v_1, v_2-$ are leaves of the tree $\Rightarrow \exists!$ a maximal independent set. Give some clue please! Thanks anyway!
2
votes
1answer
64 views

Decide probabilistically whether leaf labels in a decision tree sum to zero?

I have the following problem, which might or might not be very easy to answer for someone with even a light background in statistics - but I don't even know where to start. Hence, I will give it a ...
2
votes
1answer
140 views

Count possible traversals in an undirected graph

A graph of $n$ nodes is given. We have to visit each node twice. How many such traversals are there? It's a complete graph and it's not possible to visit the nodes in a consecutive order. Example: ...
0
votes
1answer
77 views

build a graph with smallest diameter, N verteces, each vertex has degree $\ge k$

I need to build a graph with number of vertexes N such that each vertex has degree at least k and the graph has the smallest diameter. I believe that this question should be well studied. EDIT: yes ...
1
vote
1answer
284 views

Finding all spanning trees of a strongly connected directed graph

I have a strongly connected directed graph with about 10 vertices and 20 edges, and would like to find all spanning trees anchored at each vertex. Is there a systematic way, or a tested ...
0
votes
1answer
202 views

Topological sort of a subgraph

If I have a graph $G$ and a subset $G'$, for all topological sorts $S$ over $G$, is there a topological sort over $G'$ that is a subset of $S$? As a software optimization I want to pre-compute $S$ ...
2
votes
2answers
259 views

Proof a bipartite graph problem

Prove that: a simple graph is a bipartite graph if and only if lenght of all circuits in graph be even. (give me answer or hint or idea)
2
votes
0answers
135 views

Almost regular graphs that are Hamiltonian

It is known that every $r$-regular graph on $2r+1$ vertices is Hamiltonian (Nash-Williams theorem, see here). Now, I wonder if there is a simpler way to show that the graph on $4n+3$ ($n \ge 1$) ...
2
votes
1answer
173 views

Is it possible to make a graph eulerian by adding exactly one node?

Let $G=(V,E)$ denote a connected graph with $|V|\geq 2$. Is it possible to add a new node $v$ with corresponding edges $e_k=\{v,w\}$ with $w\in V$(*1) such that $(V\cup\{v\},E^\prime)$ contains an ...
6
votes
3answers
647 views

Number of maximum components of a graph once any one vertex is removed

Let $G$ be an arbitrary graph with $n$ nodes and $k$ components. If a vertex is removed from $G$, the number of components in the resultant graph must necessarily lie between$\ldots$? I figured ...
1
vote
0answers
57 views

Can you consider a directed graph the discretization of a 2-manifold equipped with a vector field?

Can you consider a directed graph the discretization of a 2-manifold equipped with a vector field? Thanks
1
vote
2answers
353 views

Landau's Theorem on tournaments

There is a Landau's theorem related to tournaments theory. Looks like the sequence $(0, 1, 3, 3, 3)$ satisfies all three conditions from the theorem, but it is not possible for 5 people to play ...
0
votes
1answer
97 views

Proof about Graph with no triangle

For graph G without a triangle(with no triangle) with n vertices and m edges Prove that: 1)$ \forall xy \in E , d(x)+d(y) \le n$ 2)$(\sum_{v\in_V}^{ }d(v)^2)\le mn$
0
votes
1answer
121 views

Proof of a graph problem on degree sequence

Prove that: order of natural number $d_1 , d_2 , \ldots , d_n$ as descending is a ordering graph if and only if the order was sorted as descending $d_2-1, d_3 -1 , \ldots ,d_d -1,\ldots ,d_n$ be ...
0
votes
1answer
182 views

Constructing a graph based on numbers of vertices, incident edges, and incident triangles

In my project to construct the outer automorphism group for $S_6$ I have come across a need (or desire) to visualize a graph that has 15 vertices, with each vertex having 6 incident edges and 3 ...
0
votes
1answer
1k views

Kuratowski's theorem and non - planar graph

Hi I have attached two graphs. I am trying to prove that the graph is non- planar. By Kurathowski's theorem, a graph is nonplanar if and only if it contains a subgraph homeomorphic to $K_{3,3}$ or ...
0
votes
1answer
176 views

graph-theory problem about outdegree and indegree

Let g be directed graph with n vertices . Let if we remove directions in graph g (hypothesis).then we have undirected graph $k_n$. prove that : $(od(v_1))^2+(od(v_2))^2+ ... + (od(v_n))^2 = ...
2
votes
2answers
392 views

how to Compute the number of pairwise non-isomorphic 7-regular graphs on 10 vertices?

Compute the number of pairwise non-isomorphic 7-regular graphs on 10 vertices?
0
votes
2answers
217 views

Let $G=(V,E)$ be a connected graph with $|E|=17$ and for all vertices $\deg(v)>3$. What is the maximum value of $|V|$?

Let $G=(V,E)$ be a connected graph with $|E|=17$ and for all vertices $\deg(v)>3$. What is the maximum value of $|V|$? (What is the maximum possible number of vertices?)
-2
votes
1answer
2k views

Graph Theory, complements of isomorphic graphs are isomorphic

Let $G$ and $H$ be isomorphic graphs. Prove that the complements of $G$ and $H$ are isomorphic.
1
vote
1answer
227 views

Prove equivalence of conditions for a tree

Let $G=(V,E)$ denote a nonempty graph. Show that the following conditions are all equivalent. $G$ is a tree. Any two vertices in $G$ can be connected by a unique simple path. $G$ is ...
3
votes
1answer
553 views

Application of Hall's Theorem

Let $G$ be a bipartite graph, with bipartition $(X,Y)$ with no isolated vertices. Suppose that for every edge $xy$ with one end $x\in X$ and another end $y\in Y$, we have $\deg(x) \ge \deg(y)$. Prove ...
2
votes
5answers
278 views

Graph Theory Distance Algorithm

My own problem: Let G be a undirected graph with $n$ vertex and $m$ edges. We have a list that $v_{1} \rightarrow v_{2}$ but it's not important now. Every edge has a weight equal to X. Our task is ...
0
votes
1answer
34 views

In three-connected graph $G = (V, E)$ $\forall a,b,c \in V \Rightarrow a,b,c \in C$, where $C$ is simple cycle.

In three-connected graph $G = \langle V, E\rangle$, any three vertices $a,b,c \in V$ are contained in some simple cycle $C$ in $G$. Please give some clues! Thanks anyway!
2
votes
1answer
157 views

Every ${K}_{1, 3}$-free connected graph of even order has a perfect matching.

Every ${K}_{1, 3}$-free connected graph of even order has a perfect matching. Probably it can be shown using the Tutte theorem about perfect matching. Please give some clues! Thanks anyway!
0
votes
1answer
172 views

Let $G$ be a bipartite graph with bipartition $X$ and $Y$ having a matching from $X$ into $Y$.

Prove that there is a vertex $x\in X$ such that every edge incident with $x$ is contained in some matching from $X$ into $Y$.
0
votes
3answers
1k views

What is the main difference between a free tree and a rooted tree?

In graph theory what is the difference between a rooted tree and a free tree ? What is normally meant when just the plain "tree" is used ?
3
votes
1answer
260 views

The opposite category of the category of graphs

Does anyone know where I can find a description of the opposite category of the category of graphs? The morphisms of the category are graph homomorphisms. Thank you
3
votes
2answers
313 views

Matching in bipartite graphs

I'm new here. Well, actually I'm studying graph theory and the follow question is driving me crazy. Any hint in any direction would be appreciated. Here is the question: Let $G = G[X, Y]$ a ...
2
votes
1answer
665 views

Number of Automorphisms of a given Graph

Given a small graph, how can you manually calculate the number of automorphisms? I thought of seeing the number of nodes of a particular degree and permuting among them, but aren't there other factors ...
0
votes
1answer
66 views

Question related to a proof about the multiplicity of some eigenvalues

I have a question related to Lemma 4.2 from this pdf (which is, btw quite a nice exposition of Hoffman Singleton work on the classifications of Moore graphs of diameter 2 and 3.) We are given a $n ...
1
vote
2answers
109 views

quick question on showing every edge in a graph of minimum degree n+1 is contained in a hamiltonian circuit.

Show that if every vertex in a graph on $n$ vertices has degree at least $\frac{n+1}{2}$, then every edge $e\in E(G)$ in G is contained in a Hamiltonian circuit. My battle strategy: We know that ...
4
votes
1answer
1k views

Graph theory: Prove $k$-regular graph $\#V$ = odd, $\chi'(G)> k$

I'm looking to prove that any $k$-regular graph $G$ (i.e. a graph with degree $k$ for all vertices) with an odd number of points has edge-colouring number $>k$ ($\chi'(G) > k$). With Vizing, I ...
5
votes
2answers
116 views

Lower bounds on the number of edges in a nonplanar graph

Let $e$ be the number of edges and $v \geq 3$ the number of vertices in a graph $G$. We know that if $G$ is planar, then $e \leq 3v-6$. My question is the opposite. Is there some sort of inequality ...
1
vote
0answers
343 views

Understanding dependency graph for a set of events

Definition 4. Let $\mathcal{E}_1 , \mathcal{E}_2 , \dots, \mathcal{E}_n$ be n events on a probability space $Ω$. The dependency graph is a directed graph $D = (V, E)$ on the set of vertices $V = ...
2
votes
2answers
112 views

Why don't all transitive graphs with a single loop define a category?

I'm reading Abstract & Concrete Categories: The Joy of Cats. On exercise 3A(c), the author defines the graph of a category C to be the large graph whose vertices are the objects in C, and whose ...
0
votes
1answer
258 views

Difference and relation between dependency graph and graphical model?

From page 2 of http://www.mpi-inf.mpg.de/departments/d1/teaching/ss11/ProbMethod/files/lll.pdf Let $A_1 , A_2 , \dots, A_n$ be $n$ events on a probability space $Ω$. The dependency graph is a ...