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

-3
votes
1answer
11 views

existence of perfect matching in a bipartite graph with special conditions

Claim: Suppose $G(V, E)$ is a bipartite graph where $A\cup B = V$, $|A|=|B|$, every vertex has a even degree $(deg(v) \in \{2,4,6,...\})$ and no vertex is isolated. if this is the case, you can always ...
1
vote
0answers
7 views

Is the adjacency matrix of a given graph (OR any graphs isomorphic to a given graph) a Kronecker product, and if so what are the factors?

I have a few triangular grid graphs that I am trying to express as the direct products of smaller graphs, if possible. I've approached this in Mathematica by representing the graphs as their ...
0
votes
2answers
33 views

graph theory,number of edges

Let Gn be the graph with vertex set all binary strings of length n (binary strings are strings of zeros and one, for example 0110100 is a binary string of length seven). Two strings are adjacent is ...
2
votes
0answers
16 views

Is there an easy way to realize a graph (i.e. get adjacency matrix) from a fundamental cut-set or loop matrix?

I am looking to realize a graph (i.e. write down its adjacency or incidence matrix) given a fundamental cut-set matrix or loop matrix (with respect to an arbitrary spanning tree). Is there some ...
1
vote
0answers
13 views

Intuition for Laplacian matrix of a graph's eigenvectors and eigenvalues

I am having difficulty finding intuition for Laplacian matrix eigenvalues/vectors in terms of non-regular, non-complete graphs. For example, consider the L, Laplacian, on a graph, G, a set of points ...
1
vote
1answer
21 views

Proving Depth First Search

Let G be a connected graph, and let r ∈ V (G). Prove that G has a spanning tree T such that for every edge of G with ends u and v, either u belongs to the unique path in T with ends v and r, or v ...
0
votes
2answers
18 views

Every tournament conatins a hamiltonian path - question about the proof

There is a proof that every tournament contains a Hamiltonian path and it goes as follows: Let $P$ be a path of greatest length in a tournament $T$, say $P = (v_1,v_2,...,v_k)$. Let's say that there ...
1
vote
2answers
20 views

Graph Theory Edge-Disjoint Spanning Trees

I have the problem: Show that if a graph $G$ contains $k$ edge-disjoint spanning trees, then for each partition $(V_1, V_2, . . . , V_n)$ of $V(G)$, the number of edges of $G$ which have ends in ...
1
vote
0answers
17 views

Why do we care about triangle density and triangle freeness in large graphs?

There seems to be a lot of research done about determining whether large graphs are triangle free or counting the number of triangles. Aside from coloring, why is this important?
2
votes
1answer
32 views

What is an acyclic connected graph in graph theory?

I want to know What it is and whether there is a difference in the definition when looking at undirected and directed graphs?
0
votes
1answer
29 views

Software(online/offline) to draw graph theory graphs

I need a software that can draw graph by taking number of vertices , type of label and edges in the format (x y) as input eg: ...
3
votes
1answer
22 views

Self complementary graph with a pendant vertex

Show that if a self-complementary graph contains a pendant vertex, then it must have at least another pendant vertex. Let $G$ be a graph of order $n$, so it has $n(n-1)/4$ edges, just like its ...
1
vote
1answer
54 views

What are the components of binary strings?

$C_{9}$ is the graph with vertices representing all binary strings of length nine. Two strings are adjacent if and only if they differ in exactly three positions. How can I compute how many components ...
0
votes
1answer
11 views

Proving Welsh-Powell Algorithm

I'm proving a statement of Welsh-Powel Algorithm, that is, A graph can be colored by only using $\max_i (\min(d_i + 1, i))$ colors. I can understand why it contains $d_i$ but cannot understand the ...
1
vote
0answers
28 views

Can a connected regular simple graph have two maximal cliques of different order?

Can a connected regular simple graph have two maximal cliques of different order? I know of examples of regular simple graphs having two maximal cliques of different order. But will connectedness ...
0
votes
3answers
22 views

determining which graphs are bitpartite/2-colorable and which are not

I am having trouble understanding bipartite/$2$-colorable graphs. I was hoping someone can guide me through this question. For the graphs given above, either prove that they are bipartite by showing ...
3
votes
0answers
36 views

Tripartite n+1-regular graph containing a triangle

Suppose a tripartite, $(n+1)$-regular graph. Each one of its $3$ parts $(A,B,C)$ contains $n$ nodes. Show that the graph contains a triangle. I think the fact that it is $n+1$ and not $n$ plays an ...
2
votes
1answer
26 views

The output spanning tree of Kruskal's algorithm is a minimum spanning tree

I want to show that the output spanning tree $S$ of Kruskal's algorithm is a minimum spanning tree, so it is of minimum weight, by contradiction. We suppose that $S$ is not a minimum spanning tree. ...
2
votes
2answers
21 views

Proving cycles in graph

I have the problem: Let $d>1$ be an integer. Prove that if every vertex of a graph $G$ has degree at least d, then G contains a cycle of length at least $d + 1$. I'm pretty sure this can be done ...
0
votes
1answer
10 views

Proof about eulerian digraph - need help understanding one arguement

I'm trying to understand proof of the following theorem: A nontrivial connected digraph $D$ is Eulerian if and only if outdegree and indegree is equal for every vertex $v$ of $D$. This is an ...
2
votes
1answer
20 views

Proving Cayley formula using Kirchhoff matrix theorem?

To count the number of spanning trees of a complete graph of order $n$ one can use Kirchhoff matrix theorem and arrive at the exact answer $n^{n-2}$. But in doing so, one should know how to evaluate ...
1
vote
1answer
10 views

Does a subgraph of a graph have to be either induced or spanning?

I found this problem in a textbook with no answer provided: Consider a graph G. Do all subgraphs of G have to be either induced or spanning? My inclination is that they do not since (a) An ...
1
vote
1answer
6 views

Show that the number of paths of length $m$ from $i$ to $j$ is given by $(A^m)_{ij}$.

Let $G$ be a graph with adjacency matrix $A$ and let $m\geq 0$. That means, in $A$ the entries say how many edges there are between each two vertices. For example $A_{ij}=1$ means that there is 1 edge ...
0
votes
1answer
24 views

How can I draw a Hasse Diagram divisibility?

We just started learning graphs and I wanted to know how can I draw the Hasse diagram for divisibility on the sets: {$6, 10, 14, 15, 21, 22, 26, 33, 35, 39, 55, 65, 77, 91, 143$} In class we ...
1
vote
0answers
8 views

Partitioning a graph such that size of cut is maximum for number of vertices odd

Given a graph $G$ with $n$ vertices and $m$ edges, a cut $C$ of the graph are two disjoint subsets of the vertices $V_1$ and $V_2$ such that number of edges from $V_1$ to $V_2$ is maximum. This number ...
-1
votes
0answers
23 views

Is there any algorithm known to find largest set of non-adjacent vertices in a graph? [on hold]

Or any study related to this problem. Thanks in advance
2
votes
1answer
51 views

The output of Kruskal's algorithm is a spanning tree

I want to show that the output of Kruskal's algorithm is a spanning tree. Let $G$ be a connected, weighted graph and let $S$ be the subgraph of $G$ which is the output of the algorithm. $S$ cannot ...
1
vote
0answers
17 views

Coloring chordal graphs

It is well known that the graph coloring problem --- given a graph $G$ and a number $k\in\mathbb{N}$ decide whether $\chi(X)\le k$ --- is NP-complete. However, certain classes of graphs can be colored ...
1
vote
0answers
17 views

Definition of a minimal set of automorphisms generating an orbit?

By definition, the orbit of a vertex v in a graph G is the set of all vertices f (v) such that f is an automorphism of G. I wonder whether there is a definition for a minimal set S of automorphisms ...
1
vote
1answer
32 views

Topological structure/graph from a paper

This question is based off a paper titled "On designing heteroclinic networks from graphs." I'm having a difficult time visualizing something "drawn in 4-dimensions" projected down to a 2-dimensional ...
2
votes
1answer
19 views

What's the name of an 'extended' cycle graph

I'm looking for the name of a regular cycle graph, where each node is connected with it's k neighbors. In particular, I'm looking for a lemma at Wolfram Mathworld or Wikipedia. An examples of this ...
1
vote
1answer
22 views

Prove number of edges in an edge-disjoint spanning tree

I have the following problem. It isn't homework--it's additional work I want to do to further grasp the material in my Combinatorics class. Show that if a graph $G$ contains $k$ edge-disjoint ...
4
votes
1answer
73 views
+150

The graph has an Euler tour iff in-degree($v$)=out-degree($v$)

I am looking at the proof that $G$ has an Euler tour iff in-degree($v$)=out-degree($v$), that I found at this site: www.cs.duke.edu/courses/fall09/cps230/hws/hw3/headsol.pdf (Problem 2) A simple ...
-9
votes
1answer
66 views

Theory of 4 colors [on hold]

Je pense que j'ai pu trouver une contre-exemple, sur la conjecture des 4-couleurs!, Veuillez voir ca: http://cjoint.com/?EDyoaOVaS3S @@@ I think I could find a cons-example, 4-color conjecture !, ...
0
votes
0answers
18 views

Determine the value of $ex(n,P_4)$

I want to determine the exact value of $ex(n,P_4)$ I believe that the answer to this is $n$, if $n\equiv 0$ (mod $3$), and $n-1$ otherwise. Given n vertices, one can create multiples of $K_3$. If ...
0
votes
0answers
14 views

Probabilistic proof for expander existence

I am new to probabilistic proofs and trying to understand them better. Apparently, a common probabilistic proof focuses on the existence of expanders (eg. vertex expanders). I've been using the search ...
1
vote
1answer
85 views

A math contest question related to Ramsey numbers

In a group of 17 nations, any two nations are either mutual friends, mutual enemies, or neutral to each other. Show that there is a subgroup of 3 or more nations such that any two nations in the ...
2
votes
0answers
44 views

Card layouts and graph theory

I define a layout of cards to be the placement of each card arbitrarily in three dimensions, observed from a particular angle. Cards cannot be bent, folded, cut or mutilated in any way. Every layout ...
1
vote
0answers
33 views

Is there a method to measure the similarity between undirected graph vertices?

I'm doing some research on User Identity Resolution. Assume i can get two undirected graphs of a person, one is the friendship in Twitter of that person, the other ...
0
votes
0answers
8 views

Are there any minimum-degree-5 triangulations of the sphere for which every four-coloring consists of six Kempe chains, one for each color-pair?

I'm interested only in triangulations that have no separating triangles (i.e. triangles for which there are vertices both inside and outside the triangle). The 5-regular icosahedron is one. Are ...
0
votes
1answer
18 views

Hamilton-like paths in digraph

We are given digraph with two (possibly the same) vertices - let's call them S and F. We are also given some set of vertices W (possibly empty, possibly consisting of all vertices of digraph). We ...
1
vote
0answers
14 views

Task about Hartley information(logarithm from cardinality of the set) of a number of paths in a graph and about limit linked with this information.

Let $L_n$ be the number of all paths of length n in a directed graph(below). It is needed to find $lim_{n \to \infty}\chi(L_n)/n$ where $\chi(L_n)$ is Hartley information in $L_n$ set. (If I am not ...
1
vote
1answer
38 views

Number of labeled graphs satisfying a degree sequence

Say we have two sequences of integers $d^\text{in}$ and $d^\text{out}$ representing the in- and out-degree sequences of a directed graph. How many (possibly isomorphic) graphs are there that satisfy ...
0
votes
0answers
14 views

Petri Nets Elementary Circuit Algorithim

I'm lost as to how you tackle this question in the picture attached? Could someone please explain it in Lehman's terms or even just get me started? Thanks!
2
votes
0answers
62 views

Tree decomposition by hand for understanding

I am implementing "algorithm 2" from the paper "Treewidth computations I. Upper bounds" by Bodlander and Koster[1,page5] and I am not sure if I understand it or not. As I understand, the algoritm ...
1
vote
1answer
23 views

Let G be an r -regular graph with n vertices and m edges. Prove a simple algebraic relation between r , n, and m.

I know that it for any regular graph $r_{n}$ that we can show a relation between r, n, m. However, I'm not sure how to find or prove this relation. I assume that the relation will be something like ...
0
votes
0answers
46 views

Graph Combinatorics: How many such Graphs are there?

How many $4$-regular graphs exist on $8$ vertices? I found that such a graph can't be disconnectd since if so, then graph can be written as disjoint union of atleast two graphs. $4$ regularity ...
1
vote
0answers
19 views

Analogue of Fáry's theorem taking sphere and geodesics instead of plane and straight lines.

Fary's theorem states that any simple planar graph can be drawn without crossings so that its edges are straight line segments (see Wikipedia). The proof is based on the Art gallery theorem, so I ...
10
votes
1answer
216 views

Twilight Zelda Guardian Puzzle : Shortest Path (UPDATE: ADDED RULES)

I'm playing a video game right now and in it is a puzzle (see here). There are solutions to solving it (see here) on the Internet, but I'd like to know if this path is the shortest path (least amount ...
0
votes
1answer
24 views

Maximum Number of Vertices of a block-cutpoint graph

For a graph $G$ on $n \geq 1$ vertices, what is the maximum number of vertices of its block-cutpoint graph $BC(G)$? What I have so far: The block-cutpoint graph of a graph $G$ is the bipartite graph ...