WOLFRAM

Wolfram Language & System Documentation Center
Wolfram Language Home Page »

PathGraphQ
✖
PathGraphQ

✖

yields True if the graph g is a path and False otherwise.

Details

  • An undirected path graph is a connected graph where each vertex has at most degree two.
  • A directed path graph is a connected graph where each vertex has at most in-degree one and at most out-degree one.

Examples

open allclose all

Basic Examples  (2)Summary of the most common use cases

Test whether a graph is a path:

In[1]:=1
✖
https://wolfram.com/xid/0b8c5gpe7n-k4jlxo
Out[1]=1
In[2]:=2
✖
https://wolfram.com/xid/0b8c5gpe7n-f9w1u8
Out[2]=2

The vertex degree is at most 2:

In[3]:=3
✖
https://wolfram.com/xid/0b8c5gpe7n-buqt6d
Out[3]=3

A complete graph is not a path:

In[1]:=1
✖
https://wolfram.com/xid/0b8c5gpe7n-btpktr
Out[1]=1
In[2]:=2
✖
https://wolfram.com/xid/0b8c5gpe7n-28fym5
Out[2]=2

The vertex degree is greater than 2:

In[3]:=3
✖
https://wolfram.com/xid/0b8c5gpe7n-idj4eo
Out[3]=3

Scope  (6)Survey of the scope of standard use cases

PathGraphQ works with undirected graphs:

In[1]:=1
✖
https://wolfram.com/xid/0b8c5gpe7n-fgkyo1
Out[1]=1

Directed graphs:

In[1]:=1
✖
https://wolfram.com/xid/0b8c5gpe7n-gx301e
Out[1]=1

Multigraphs:

In[1]:=1
✖
https://wolfram.com/xid/0b8c5gpe7n-uvnf7h
Out[1]=1

Mixed graphs:

In[1]:=1
✖
https://wolfram.com/xid/0b8c5gpe7n-bjkwbz
Out[1]=1

PathGraphQ gives False for anything that is not a path graph:

In[1]:=1
✖
https://wolfram.com/xid/0b8c5gpe7n-3l2bwe
Out[1]=1
In[2]:=2
✖
https://wolfram.com/xid/0b8c5gpe7n-i52fbz
Out[2]=2

Test large graphs:

In[1]:=1
✖
https://wolfram.com/xid/0b8c5gpe7n-pq9ae
In[2]:=2
✖
https://wolfram.com/xid/0b8c5gpe7n-cevvx1
Out[2]=2
In[3]:=3
✖
https://wolfram.com/xid/0b8c5gpe7n-g0lnwq
Out[3]=3

Properties & Relations  (8)Properties of the function, and connections to other functions

A path graph is loop-free if it has more than one vertex:

In[2]:=2
✖
https://wolfram.com/xid/0b8c5gpe7n-roqnm
Out[2]=2
In[3]:=3
✖
https://wolfram.com/xid/0b8c5gpe7n-g0013
Out[3]=3

A path graph does not necessarily have edges:

In[1]:=1
✖
https://wolfram.com/xid/0b8c5gpe7n-k4ile7
Out[1]=1

A path graph that starts and ends in the same vertex is a cycle graph:

In[1]:=1
✖
https://wolfram.com/xid/0b8c5gpe7n-elsy02
Out[1]=1
In[2]:=2
✖
https://wolfram.com/xid/0b8c5gpe7n-bzbx5p
Out[2]=2

A path graph with no repeated vertices is a tree:

In[1]:=1
✖
https://wolfram.com/xid/0b8c5gpe7n-eik333
In[2]:=2
✖
https://wolfram.com/xid/0b8c5gpe7n-j4l391
Out[2]=2

An acyclic path graph is simple:

In[1]:=1
✖
https://wolfram.com/xid/0b8c5gpe7n-dk1zp0
Out[1]=1
In[2]:=2
✖
https://wolfram.com/xid/0b8c5gpe7n-hrens
Out[2]=2

And also bipartite:

In[3]:=3
✖
https://wolfram.com/xid/0b8c5gpe7n-j4bb1c
Out[3]=3

GridGraph[{1,…,1,k,1,…,1}] are all path graphs:

In[1]:=1
✖
https://wolfram.com/xid/0b8c5gpe7n-c7puie
Out[1]=1
In[2]:=2
✖
https://wolfram.com/xid/0b8c5gpe7n-c1by62
Out[2]=2
In[3]:=3
✖
https://wolfram.com/xid/0b8c5gpe7n-oaset
Out[3]=3

A path graph is connected and each vertex has at most degree 2:

In[1]:=1
✖
https://wolfram.com/xid/0b8c5gpe7n-cvi52e
Out[1]=1
In[2]:=2
✖
https://wolfram.com/xid/0b8c5gpe7n-dn4w0f
Out[2]=2
In[3]:=3
✖
https://wolfram.com/xid/0b8c5gpe7n-gh1tvf
Out[3]=3

The line graph of a path is isomorphic to :

In[1]:=1
✖
https://wolfram.com/xid/0b8c5gpe7n-e93bcs
Out[1]=1
In[2]:=2
✖
https://wolfram.com/xid/0b8c5gpe7n-o73fsf
Out[2]=2

Possible Issues  (1)Common pitfalls and unexpected behavior

PathGraphQ gives False for non-explicit graphs:

In[1]:=1
✖
https://wolfram.com/xid/0b8c5gpe7n-nd8s9y
Out[1]=1
In[2]:=2
✖
https://wolfram.com/xid/0b8c5gpe7n-iu6w07
Out[2]=2
Wolfram Research (2010), PathGraphQ, Wolfram Language function, https://reference.wolfram.com/language/ref/PathGraphQ.html.
✖
Wolfram Research (2010), PathGraphQ, Wolfram Language function, https://reference.wolfram.com/language/ref/PathGraphQ.html.

Text

Wolfram Research (2010), PathGraphQ, Wolfram Language function, https://reference.wolfram.com/language/ref/PathGraphQ.html.

✖
Wolfram Research (2010), PathGraphQ, Wolfram Language function, https://reference.wolfram.com/language/ref/PathGraphQ.html.

CMS

Wolfram Language. 2010. "PathGraphQ." Wolfram Language & System Documentation Center. Wolfram Research. https://reference.wolfram.com/language/ref/PathGraphQ.html.

✖
Wolfram Language. 2010. "PathGraphQ." Wolfram Language & System Documentation Center. Wolfram Research. https://reference.wolfram.com/language/ref/PathGraphQ.html.

APA

Wolfram Language. (2010). PathGraphQ. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/PathGraphQ.html

✖
Wolfram Language. (2010). PathGraphQ. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/PathGraphQ.html

BibTeX

@misc{reference.wolfram_2025_pathgraphq, author="Wolfram Research", title="{PathGraphQ}", year="2010", howpublished="\url{https://reference.wolfram.com/language/ref/PathGraphQ.html}", note=[Accessed: 04-April-2025 ]}

✖
@misc{reference.wolfram_2025_pathgraphq, author="Wolfram Research", title="{PathGraphQ}", year="2010", howpublished="\url{https://reference.wolfram.com/language/ref/PathGraphQ.html}", note=[Accessed: 04-April-2025 ]}

BibLaTeX

@online{reference.wolfram_2025_pathgraphq, organization={Wolfram Research}, title={PathGraphQ}, year={2010}, url={https://reference.wolfram.com/language/ref/PathGraphQ.html}, note=[Accessed: 04-April-2025 ]}

✖
@online{reference.wolfram_2025_pathgraphq, organization={Wolfram Research}, title={PathGraphQ}, year={2010}, url={https://reference.wolfram.com/language/ref/PathGraphQ.html}, note=[Accessed: 04-April-2025 ]}